今天是动态规划的第一天！
回顾一下贪心算法是由局部最优推出整体最优，因为每一步都相对而言比较简单。而正因为贪心的性质，所以使用面也相对较窄，只能用于符合贪心性质的问题。
与贪心算法的区别在于：
动态规划是将复杂的问题拆分成更小的子问题，然后在求小问题的解的基础上构建出原问题的答案。所以一般DP是从小问题逐渐解到原问题的。也正因为解决小问题时同样可能有较为复杂的情况，所以一般动态规划会记录 解决小问题期间的值，因此相比贪心算法而言，DP消耗的空间一般会更多。
动态规划的基础结构：五部曲。
- 确定dp数组的含义。例如dp[i]表示斐波那契数列中第i个数的值
- 确定递推公式。例如在斐波那契数列中是如何由前面的数推出后面的数的：dp[i] = dp[i-1] + dp[i-2]; // 那就是由前两个数的和推出第三个数
- 初始化dp数组。例如在斐波那契数列题中，就初始化第一个数和第二个数 就足矣支持后续的计算。
但是在有些题中，会需要初始化整个数组。具体情况需根据正确理解来分析。 - 确定遍历顺序。遍历顺序也很重要，要找对方向才能正确输出结果。例如斐波那契数列题中，就是要从前往后遍历，因为数字就是从前往后慢慢计算的，你得先有前边的结果，才能计算得出后面的值。
- 举例推导dp数组。这一步是验证了，就是当你需要检验时，（无论是你运行结果有误，还是写完之后想自己测试一下），都可以使用打印dp数组的方法来查看结果，看看打印出来的结果与预想的结果是否相同。如果不相同，再去根据打印出来的结果分析是哪一步出现了问题。
题目链接：509. 斐波那契数
状态：套用模版，直接AC。
动态规划五部曲：上面👆讲基础结构的时候已经说过了，所以这里写简单一点
- dp[i]表示数列中第i个数的值
- 递推公式是前两个数的和等于第三个数。因此dp[i] = dp[i-1] + dp[i-2]
- 初始化。dp[0] = 0; dp[1] = 1; (其实用dp[1] = 1; dp[2] = 1; 也可以 但是后续遍历的时候，i要从2变成3 作为开始)
- 遍历。从头开始遍历，但是因为有dp[i-2]的存在，所以得保证i >= 2，因此就是for(int i = 2; i <= n; i++){递推公式}
- 想测试的话可以打印。
综上所述，完整代码如下:
class Solution { // Java
public int fib(int n) {
if(n <= 1) return n;
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];
// System.out.println(dp[i]);
}
return dp[n];
}
}
可以看到，代码还是比较短的，动态规划的代码就是这样，比较短。我的理解是 那是因为 算法的核心都在找寻递推公式里了，换句话说递推公式找的妙，才使得动态规划的题目的代码少，这就充分的体现了数学思维的奇妙之处。
复杂度分析：
时间复杂度：O(n). 循环了n-1次，每次都是一个加法。
空间复杂度：O(n). n+1大小的数组。其余都是O(1)的引用。
题目链接：70. 爬楼梯
状态：开始上难度了，第一次自己看的时候没想到递推公式，看到解析后恍然大悟，然后直接AC。
这题关键在于想递推公式，正如上题所说，充分体现数学思维的时候到了。
首先题目说了每次可以选择爬1或2个台阶。因此我们在到达第m个台阶时，可以认为是 要么从第m-1个台阶爬一步得来，要么是从第m-2个台阶爬两步得来。所以爬m阶的方法总数 等于 爬m-1阶的方法总数 加 爬m-2阶的方法总数。
但是递推公式的表达还需要dp数组的含义，所以我们定义dp[i]表示到第i阶楼梯时 共有多少种方法。
结合递推公式和dp数组及下标i的含义，就可以写出表达式了：dp[i] = dp[i-1] + dp[i-2].一看好像和斐波那契数列是一样的，没错！
动态规划五部曲：
- dp[i]表示 爬i阶楼梯 共有dp[i]种方法
- 递推公式 根据上述分析：因此dp[i] = dp[i-1] + dp[i-2]
- 初始化。dp[0]没有任何实际意义，所以从dp[1]开始， dp[1] = 1，因为上1阶台阶只有一种方法；dp[2] = 2， 两种方法分别是从0阶 一次上两步/两次 每次上一步。
- 遍历。从头开始遍历，但是因为有dp[i-2]的存在，所以得保证i >= 2，因此就是for(int i = 3; i <= n; i++){递推公式}。 从3开始是因为i=2的时候已经被定义了，再参与计算就会出错。
- 想测试的话可以打印。
综上所述，完整代码如下:
class Solution { // Java
public int climbStairs(int n) {
if(n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
代码几乎和上面一样。复杂度分析也相同。但是做题时感觉第二题会明显比第一题难多了。这是因为第一题 斐波那契数，他把初始化条件和递推公式都直接在条件里告诉你了，所以写起来得心应手。而第二题里，递推公式需要自己分析得出。那么在第二题 爬楼梯 的基础上我们再来继续第三题：
题目链接：746. 使用最小花费爬楼梯
状态：直接AC。
在第二题的基础上这题会好想很多。本题是在爬楼梯的基础上增加了一个 体力消耗 的规则。因此我们的dp数组的含义也相对应的要改为 爬到第i阶楼梯时 所消耗的体力数。
那同样的，爬到第i阶楼梯消耗的体力数 = 爬i-1阶楼梯消耗的体力 + 第i-1阶楼梯到第i阶楼梯消耗的； 或者 爬i-2阶楼梯消耗的体力 + 爬第i-2阶楼梯到第i阶楼梯消耗的。
因为我们是要求最小值，所以只需每次比较这两者的大小，然后取小的就好了。
动态规划五部曲：
- dp[i]表示 爬i阶楼梯 共消耗的体力数
- 递推公式 根据上述分析：因此dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
- 初始化。dp[0] = 0, dp[1] = 0，因为开始可以选择站在0号或1号台阶，同时题目明确了规则：不起跳就不消耗体力
(我在代码里是把整个数组的值都初始化成0了 然后额外修改了dp[0]和dp[1]的值，但是因为后续循环里会改i>=2以后的值，所以无伤大雅） - 遍历。从头开始遍历，i从2开始，遍历长度为cost列表长度。这是保证能最后要到达台阶顶端
- 想测试的话可以打印。
完整代码如下：
class Solution: // Python
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = [0] * (len(cost) + 1)
dp[0] = 0 #初始值
dp[1] = 0
for i in range(2, len(cost) + 1):
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
return dp[len(cost)]
复杂度分析：
时间复杂度：O(n). 循环了 len(cost) - 1 次，循环内是O(1)， 所以做乘法 还是O(n)
空间复杂度：O(n). len(cost) + 1 大小的数组。其余都是O(1)的引用。
