动态规划理论基础
递归算法是一种穷举的展示，任何数学递推公式都可以直接转换成递归算法，递归算法是当前层需要上一层的准备。递归算法冗余计算的增长是爆炸性的。如果编译器的递归模拟算法要是能够保留一个预先算出的值的表，而对已经解过的子问题不用再进行递归调用，那么这种指数式的爆炸性的增长就可以避免
动态规划就是这样的算法
如果某一个问题可以解决很多重叠问题，那么使用动态规划是最有效的解决办法
动态规划中的每一个状态是由上一个状态推导出来的，这和贪心算法是不同的，贪心算法是没有状态推导的过程，贪心算法都是在当前局部选取最优解。所以贪心算法解决不了动态规划的问题
动态规划五部曲：
1、确定dp数组（dp table）及下标的含义
2、确定递推公式
3、初始化dp数组
4、确定遍历顺序
5、举例推导dp数组
509. 斐波那契数
题目链接：力扣
思路
下面是对递归的优化：
用表优化递归
从这道题目可以看出，递归算法是需要不断向下进行计算，进行压栈，比如要算F(5)，那就要先算出F(4)和F(3)，就要先算出F(3)、F(2)、F(2)、F(1)……，这里可以看到是有重复的运算的
那我们可以先创建一个数组（表），能够保留一个预先算出的值，这样就可以不用，这样就避免了重复的运算。已经算过的F(n)就不用再进行重复的计算
根据动态规划五部曲：
1、确定dp数组（dp table）及下标的含义
第i个下标存储的是F(i)斐波那契的值
2、确定递推公式
递推公式是：dp[i] = dp[i - 1]+dp[i - 2]
3、初始化dp数组
dp[0] = 0;
dp[1] = 1;
4、确定遍历顺序
从递推公式可以得出，后面的数字依赖前面的数字，所以是从前向后遍历
5、举例推导dp数组
0 1 1 2 3 5 8 13 21 34 55
下面是对表的优化：
得出动态对话的代码之后会发现，代码的内存消耗比较大，我们发现处理，中间过程中的数字不都用，但是还是占用了内存，这样的内存占用时浪费的。比如F(10)。dp数组为：0 1 1 2 3 5 8 13 21 34 55。但是只会返回55，前面的都不用
其实只需要维护两个数值就可以了，不需要记录整个数列。在整个遍历的过程中
dp[0] = dp[i - 1]
dp[1] = dp[i - 2]
最后循环结束的时候dp[1]就是我们要的值
斐波那契数
递归思路
class Solution { public int fib(int n) { // 终止条件 if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); } }
动态规划
class Solution { public int fib(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } // 创建数组 int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }
动态规划(优化数组)
class Solution { public int fib(int n) { if (n <= 1) { return n; } // 创建数组 int[] dp = new int[2]; // 初始化数组 dp[0] = 0; dp[1] = 1; // 遍历实现数组 for (int i = 2; i <= n; i++) { int sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return dp[1]; } }
