动态规划总括

如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的由此来判断是否使用动态规划

动规是由前一个状态推导出来的，而贪心是局部直接选最优的
动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

对于动态规划问题，我将拆解为如下五步曲：

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

动态规划应该如何debug：
找问题的最好方式就是把dp数组打印出来，看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

解题：
首先思考这是一个动态规划的题目，那么当前值是由前面的值表示出来的，怎么表示呢?不清楚。此时就应该通过答案反推过程同时在此过程中要始终记得当前值是可以由前面的值表示的。
dp[ n ] = 某某+dp[ i ]
dp[ i] = 某某+dp[ i] +/-/*/÷ dp[ j ]