方法论

方法论

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

dp五步曲

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

注意：

dp 初始化 case 的情况，一般要放在函数开头前单独处理，防止dp数组index越界....

比如，509. 斐波那契数 if (n <= 1) return n; 需要单独处理。

否则，当n==1时，初始化访问dp[1]数组将越界...

dp debug方法

打印 dp 数组日志，并查看与自己想模拟的dp值是否一致

若 dp 值与自己模拟的结果一致，说明是 dp五步曲中的2、3、4步骤出现问题；

若 dp 值与自己模拟的结果不一致，说明是自己代码细节有问题

做 dp 题目之前，一定要把状态转移在 dp 数组的上模拟一遍，心中有数，确定最后推出的是想要的结果。

初识DP