本节主要参考：代码随想录

题目分类

动态规划释义

动态规划，英文：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])。

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

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

动态规划的解题步骤

动态规划都需要递推公式，而递推公式的定义又很容易搞混或者不清不楚的就过去了，提交代码运行通过就不会去关心这个是怎么定义的，要是不通过就改改改，很少回去思考这个递推公式真正的含义是什么，所以动态规划可以制定五步曲，每一步按照这个来做，思路会清晰很多，当遇到问题或者想不明白的时候，就回忆一下递推公式的含义是什么。

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

遇到问题时可以从以下角度去提问题思考，其实可以自己先思考这三个问题：

• 这道题目我举例推导状态转移公式了么？
• 我打印dp数组的日志了么？
• 打印出来了dp数组和我想的一样么？