动态规划（DP）
动态规划，常用于：数学，管理科学，计算机科学，经济和生物信息学。
特征：一个问题，可以拆分成一个一个的子问题，解决子问题，顺带解决这个问题
核心思想：拆分子问题，记住过程，减少重复运算。
例子
1+1+1+1+1+1=? 等于6
在上面式子的再加上一个“ 1+”。答案是多少？
直接通过以往计算过的答案，再加1
例题：青蛙跳阶问题：
一只青蛙，可以一次跳上1级台阶，也可以一次跳上2级台阶。求这只青蛙跳10级台阶有多少种跳法？
分析：
要跳到第10级台阶，要么从第8级台阶，跳2级到第10级。要么从第9级跳1步到第十级。
要跳到第9级：可以从第8级跳1步到达，也可以从第7级跳两步到达。
要跳到第8级：可以从第7级跳1步到达，也可以从第6级跳两步到达。
............
方法一：暴力递归
//暴力递归 //时间复杂度=解决子问题的时间*子问题个数(存在大量重读运算) public class 青蛙跳阶 { public static void main(String[] args) { long l1 = System.currentTimeMillis(); int ways = ways(30); long l2 = System.currentTimeMillis(); System.out.println("有" + ways + "种跳法"); System.out.println(l2 - l1); } public static int ways(int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } return ways(n - 1) + ways(n - 2); } }
该方法时间复杂度过大，程序运行速度较慢，考虑使用数据字典进行优化
方法二：使用数据字典存储子问题的解(暴力递归的优化)
public class 青蛙跳阶_数据字典优化 { public static void main(String[] args) { long l1 = System.currentTimeMillis(); int ways = ways(30); long l2 = System.currentTimeMillis(); System.out.println("有" + ways + "种跳法"); System.out.println(l2 - l1); } static Map<Integer, Integer> map = new HashMap(); public static int ways(int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } if (map.containsKey(n)) { return map.get(n); } else { map.put(n, ways(n - 1) + ways(n - 2)); return map.get(n); } } }
方法三：动态规划
动态规划和带字典的递归有些不同，但解法类似。都有减少重复运算。
动态规划的特征：
最优子结构：f(n) = f(n-1) + f(n-2), f(n-1)和 f(n-2)就是f(n)的最优子结构。
状态转移方程：f(n) = f(n-1) + f(n-2)
边界：f(1) =1 ,f(2) = 2
重叠子：重复的运算：f(10) = f(9) + f(8),f(9) = f(8)+f(7). f(8)就是重叠子
public class 青蛙跳阶_动态规划 { public static void main(String[] args) { System.out.println(ways(10)); } public static int ways(int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } int a = 1; int b = 2; int temp = 0; for (int i = 3; i <= n; i++) { temp = a + b; a = b; b = temp; } return temp; } }
动态规划的解题思路
什么样的问题适用动态规划？
如果一个问题，可以把所有的答案穷举出来，而且存在重叠子问题，就可以考虑使用动态规划。
动态规划的经典应用场景：
最长递增子序列 ---20年蓝肽子问题
最小距离 --- 数字三角形
背包问题
凑零钱问题
等等等。。。
动态规划的解题思路
核心思想：拆分子问题，记住过程，减少重叠子运算
穷举分析
确定边界
找出规律，确定最优子结构
写出状态转移方程
代码实现
