动态规划理论基础¶

什么是动态规划¶

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

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

例如：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

不需要记住课本上动态规划的理论，只要知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。

上述提到的背包问题，后序也会具体提到。

动态规划的解题步骤¶

做动规题目的时候，并不是简单把状态转移公式背下来就开始写代码，甚至把题目AC之后，都不太清楚dp数组和dp数组每一个元素及对应的下标表示的是什么。状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。

动态规划的题目需要考虑下面五个问题：

1. 确定dp数组以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 打印dp数组判断是否符合预期

注意先确定递推公式，然后在考虑初始化呢，因为一些情况是递推公式决定了dp数组要如何初始化。后面的练习也需要考虑这五个问题。从这五步可以看出，其实确定递推公式仅仅是解题里的一步而已。

动态规划应该如何debug¶

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！

对于dp的学习绝不能是黑盒的状态，就是不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改。

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。