事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。 -《背包九讲》
概念
最优子结构: 如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构。
无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
重复子问题: 即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
状态转移方程: 描述了一种原问题与系问题的组合关系。
解决动态规划问题最难的地方有两点：
- 如何定义f(n)
- 如何通过f(1), f(2), … f(n - 1) 推导出 f(n)，即找出状态转移方程
通常思路有如下几种：
- 递归
- 自顶向下（记忆化）
- 自底向上（迭代）
动态规划问题分类
主要可以分为这几类：线性，区间，树形，状态压缩。
线性
线性类题目主要有单串、双串及矩形三类，他们的转移方程有如下特点。
单串
\[dp[i] = f(dp[i-1], dp[i-2], ... , dp[0])\]双串
\[dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])\]矩形
\[dp[i][j] = f(dp[i-1][j], dp[i][j-1])\]前缀和
区间动态规划
区间动态规划的状态设计，状态转移都与线性动态规划有明显区别，但是由于这两种方法都经常用在单串问题上，拿到一个单串的问题时，往往不能快速地判断到底是用线性动态规划还是区间动态规划，这也是区间动态规划的难点之一。但是这个难点也是好解决的，就是做一定数量的练习题，因为区间动态规划的题目比线性动态规划少很多，并且区间动态规划的状态设计和转移都比较朴素，变化也比线性动态规划少很多，所以通过不多的题目数量就可以把区间动态规划常见的方法和变化看个大概了。
状态转移，推导状态 dp[i][j] 时，有两种常见情况
dp[i][j]仅与常数个更小规模子问题有关dp[i][j]与 O(n) 个更小规模子问题有关
状态压缩动态规划
典型问题：旅行商问题
计数问题
动态规划中的计数型问题就是利用动态规划的算法思想去计算出解决这个问题有多少种方法。 比如，从起点走到终点，可以有多少条路径，注意，是多少条，而不是具体路线的描述。 当然也有具体每一条路线的问法，这是dfs的问题了。
典型问题：卡特兰数、铺砖问题
矩阵快速幂
数位动态规划
动态规划vs分治vs贪心
分治
这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题。
贪心
关于最优子结构
贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解
关于子问题最优解组合成原问题最优解的组合方式
贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案
结果正确性
贪心不能保证求得的最后解是最佳的，复杂度低
动态规划本质是穷举法，可以保证结果是最佳的，复杂度高
| 分治 | 动态规划 | 贪心 | |
|---|---|---|---|
| 适用类型 | 通用 | 优化 | 优化 |
| 子问题 | 每个都不同 | 有很多重复 | 只有一个 |
| 最优子结构 | 没有要求 | 必须满足 | 必须满足 |
| 子问题数 | 全部都要解 | 全部都要解 | 只解一个 |
典型问题
300.
Appendix
本文引用部分来自 作者：力扣 (LeetCode) 链接：https://leetcode-cn.com/leetbook/read/dynamic-programming-1-plus/xcrktd/ 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。