动态规划(Dynamic Programming)动态规划是用来求解具有最优子结构性质问题的一种方法。通俗的来说如果一个问题可以分成多个子问题或者分成多个步骤，每个子问题有多个解或者每个步骤有多个选择，最终求整体问题的一个最优解（最大值，最小值，方法总数，是否可行等等），这样的问题就适合用动态规划来求解。
动态规划一般可分为自顶而下式和自下而上式，自顶而下是通过递归，但因为涉及大量重复计算而导致时间复杂度过高，所以一般都是采用自下而上式，借助额外的空间来缓存子问题的解，减少重复计算从而降低时间复杂度，与记忆化搜索有点类似。
动态规划的适用范围
最优子结构性质
最优子结构特性（Optimal Substructure）是指一个问题可以分成多个子问题，每个问题的最优解凑成整个问题的最优解。
重叠子问题性质
重叠子问题(Overlapping subproblems)是指一个问题可以分成多个子问题，每个子问题的解会重复使用多次，也就说后一个子问题的解需要使用到前一个子问题的解。最为典型的就是Fibonacci数列，也就是常说的自上而下的方式来实现动态规划（递归式），因为子问题重复，所以为了提升效率必须把子问题的解存储下来以防止重复计算。
寻找状态转移方程
动态规划并不像排序或者二分查找那样有具体的形式，它更是一种策略而非具体的算法，发现一个题目可以用动态规划求解时，还远远不够，要想写出代码，必须推导出来状态转移方程，这才是动态规划的核心，而动态如何定义，又如何转移要视具体的问题而定变化万千，所以说动态规划是最难的一类题，没有之一。
何谓状态，状态是一个标量，是一个计算结果，比如长度，和，积，极值，数量等都是状态。
一般而言状态转移方程要以结果为导向，也就是说用这个方程能得到问题的解，这依然是一句废话，要通过大量的练习才能掌握。比如像经典的打家劫舍，f(i)为到第i个房子时所能获得的最大价值，f(n)通常为问题的解。
有些时候，不能直接得到问题的解，而是要再在状态方程f(i)之外，再叠加一个全局最优解（如全局最大值，最小值），通常子串子序列的问题都是此类，状态f(i)定义为到i时的最长子串或者子序列，但f(n-1)并不是全局的最优解，这时再在状态基础之上求个全局最优解就可以了，如最长有效括号。
动态规划有两种实现方式，一是『自上而下』的递归式，就是先思考问题的解是什么，然后思考什么是子问题，然后把问题的解递归到子问题上面，当然递归必然涉及重复计算的问题，所以要用『记忆化搜索（Memoization）』来缓存中间结果；另一个就是『自下而上』的递推，动态规划默认都是用状态转移方程来递推，也就是『自下而上』式。但有些时候，直接往递推上想可能不容易。这时不妨先考虑『自上而下』式的递归，考虑到底啥是子问题，先用递归来解决，这时通常能识别到子问题，以及问题与子问题的关系，这个关系稍加变幻就是递推式，这样状态转移方程自然就找到了。
状态方程的参数
状态的定义不同，解题的方式也就不同，对应的时间复杂度也会不同。题300和题354是最好的例子，常规状态是O(n2)，但改变状态定义后可以优化到线性（O(n)）。
如前所述，状态是一个标量，是一个函数的计算结果。这个函数的参数就相当的重要的了，因为不同的参数必然对应着不同的计算结果，状态转移也都是针对 参数的，由一个参数来求得另外一个参数。
参数也必然与输入数据有关系，通常有三种关系：
- 与输入字符串的长度有关系。通常是涉及字符串的，如切割，子序列，子串等，状态的参数都是子串或者子序列的长度。长度为0即是空串，长度为n是整个字符串。因此状态的长度通常是字符串长度加1。
- 索引位置有关系。最为典型的就是打家劫舍和多状态类的。索引位置是起决定性作用的。大部分数组类的，以及树形的，都是与索引相关。元素值往往是作为状态。
- 与元素值相关，与位置基本不相关。这类型最大的特点是状态数组并不是与原数组一一对应的，因为状态数组是用原数组的元素作为参数。典型示例是题300和题354的线性解法。以及题1218。通常并不用数组来存储状态，因为索引 并不与原数组对应。通常用列表或者哈希表来存储状态。
动态规划的分类总结
动态规划问题博大深精，甚至有人说万物皆可DP，意思是说几乎所有的题都可以用动态规划来求解。可以根据几个维度来对动态规划进行分类总结：一是看输入数据结构，是一维的数组列表，还是二维的矩阵或者树或者邻接表，当然还有双一维的输入。二是看时间复杂度是线性（即O(n)）的还是二次的（即O(n2)）。为什么要这样来分，因为这样分了之后就会有共性，能总结出一些经验。
还需要注意，动态规划总是要使用额外的空间来存储状态，一般来说空间复杂度与输入数据的维度是一致的，比如对于一维输入，一维的空间复杂度就够了（O(n)），即使有些会用到二维空间复杂度，但也可以优化到一维。
一维一次
也就是输入是一个一维数组，且用线性时间和线性空间就能解决的动态规划问题。这一般是入门级别的问题。
这种问题最为明显的特点是状态转移方程只跟前后相邻的元素有关系，或者最多是前前一个元素有关系，并且状态转移方程肯定只有一个参数。f(i) 通常能由f(i-1)或者f(i-2)推导而来。最最典型的例子就是爬楼梯和打家劫舍。
还要注意，有些问题的解并不是直接从状态方程得到，通常是子串或者子序列的状态问题，这时状态定义仍是以[i]为结束的子串或者子序列为基础去定义，但问题的解再在状态基础上求个全局最优解即可。如题32 最长有效括号。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 32. 最长有效括号 | 题解 | 状态的全局最大值为问题的解 |
| 53. 最大子数组和 | 题解 | |
| 70. 爬楼梯 | 题解 | |
| 91. 解码方法 | 题解 | |
| 198. 打家劫舍 | 题解 | |
| 213. 打家劫舍 II | 题解 | |
| 740. 删除并获得点数 | 题解 | 打家劫舍变种 |
| 746. 使用最小花费爬楼梯 | 题解 | |
| 1014. 最佳观光组合 | 题解 | |
| 题解 | ||
| 题解 | ||
| 题解 |
一维一次 多状态
有些时候定义一个状态不足以解决问题，这时就需要定义多个状态，多个状态之间也会相互影响，最为典型的就是粉刷房子。
通常都是因为元素的性质约束，或者其他条件约束，导致每一步会有多种选择，比如从前面的不同的状态走到这步，这时就要考虑定义多个状态。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 剑指 Offer II 091. 粉刷房子 | 题解 | |
| 122. 买卖股票的最佳时机 II | 题解 | |
| 123. 买卖股票的最佳时机 III | 题解 | |
| 152. 乘积最大子数组 | 题解 | |
| 188. 买卖股票的最佳时机 IV | 题解 | 终极多状态 |
| 309. 最佳买卖股票时机含冷冻期 | 题解 | |
| 714. 买卖股票的最佳时机含手续费 | 题解 | |
| 1824. 最少侧跳次数 | 题解 | 典型一维多状态，与粉刷房子类似 |
| 2786. 访问数组中的位置使分数最大 | 题解 | 奇偶性质，决定两个状态 |
| 题解 | ||
| 题解 |
一维二次
输入是一维，但是时间复杂度会上升到O(n2)。原因在于当前的状态f(i)与其前面的所有状态都有可能有关系，通常f(i)是前面状态的一种极值，或者累加。状态转移方向一般为f(i) = max{f(j), 0<=j<i}。因为对于每一个状态，都要遍历一次其前面的所有状态，以寻找满足某种约束条件的结果，所以时间复度会上升到O(n2)。典型的问题是背包问题和子序列问题。
背包问题是典型的一维二次问题，关于背包问题，单独总结了一篇文章。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 45. 跳跃游戏 II | 题解 | |
| 55. 跳跃游戏 | 题解 | |
| 300. 最长递增子序列 | 题解 | |
| 343. 整数拆分 | 题解 | |
| 376. 摆动序列 | 题解 | |
| 403. 青蛙过河 | 题解 | 步长是有隐含的约束 |
| 410. 分割数组的最大值 | 题解 | |
| 486. 预测赢家 | 题解 | 理解DP的精髓 |
| 673. 最长递增子序列的个数 | 题解 | |
| 873. 最长的斐波那契子序列的长度 | 题解 | |
| 1388. 3n 块披萨 | 题解 | |
| 1964. 找出到每个位置为止最长的有效障碍赛跑路线 | 题解 | 题300的变体 |
| 题解 | ||
| 题解 | ||
| 题解 |
一维二次叠加缓存优化
某些一维二次，就是当前状态与其前面的所有状态都可能相关，但是否相关的判断并不是O(1)的，通常需要借助缓存来防止重复计算以降到O(1)。最为典型的就是字符串回文类的问题，以及字符串分割类的问题。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 132. 分割回文串 II | 题解 | |
| 题解 | ||
| 题解 |
双一维二次
输入是两个一维数组（或者序列或者字符串），因为输入是两个一维的，必然是要按个遍历一次，所以时间复杂度不可能小于二次（O(mn)），其中m和n是两个一维数组的和度。通常空间复杂度都有优化到一维。最为典型的例子就是两个字符串的最长公共子序列。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 10. 正则表达式匹配 | 题解 | |
| 72. 编辑距离 | 题解 | |
| 392. 判断子序列 | 题解 | |
| 516. 最长回文子序列 | 题解 | |
| 583. 两个字符串的删除操作 | 题解 | |
| 718. 最长重复子数组 | 题解 | |
| 1143. 最长公共子序列 | 题解 | |
| 1312. 让字符串成为回文串的最少插入次数 | 题解 | |
| 题解 | ||
| 题解 |
二维二次
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 剑指 Offer 47. 礼物的最大价值 | 题解 | |
| 62. 不同路径 | 题解 | |
| 64. 最小路径和 | 题解 | |
| 120. 三角形最小路径和 | 题解 | |
| 174. 地下城游戏 | 题解 | 与常规方向相反 |
| 221. 最大正方形 | 题解 | |
| 787. K 站中转内最便宜的航班 | 题解 | |
| 799. 香槟塔 | 题解 | |
| 813. 最大平均值和的分组 | 题解 | |
| 1735. 生成乘积数组的方案数 | 题解 | 质因子，隐藏的维度 |
| 1928. 规定时间内到达终点的最小花费 | 题解 | 787的变种 |
| 题解 | ||
| 题解 |
区间DP
这是比较难的一类DP，状态是由一个区间约束。前面的DP的状态都是由一个位置来约束，通常定义一个f(i)就可以，即使是二维列表，每个列表也只由一个位置来决定状态。但区间问题必须 由一个区间来决定状态，单靠一个位置无法确定它的状态。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 5. 最长回文子串 | 题解 | |
| 87. 扰乱字符串 | 题解 | |
| 312. 戳气球 | 题解 | 区间DP，二维状态 |
| 3040. 相同分数的最大操作数目 II | 题解 | |
| 题解 | ||
| 题解 |
树形DP
通常DP涉及的数据结构都是线性的数组或者字符串，或者二维的矩阵。但也有其他的数据结构，树形DP是指以树（通常是二叉树）为数据结构的DP算法。
因为树的遍历只能是从根开始，先父节点再子节点，因此DP的状态转移方程只能从父节点递推而来。通常涉及两个状态，再叠加一些约束条件，约束条件都是父节点与子节点之间的约束条件。
再有就是，树形DP的递推过程并不是线性的，无法用常规的数组来保存状态。状态一般都是跟节点绑定的，所以最常用的方式是用哈希表来存储状态，以节点为键值，值为节点对应的状态，保存在哈希表中。如果是两个状态，则需要两个哈希表。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 337. 打家劫舍 III | 题解 | |
| 1372. 二叉树中的最长交错路径 | 题解 | |
| 1857. 有向图中最大颜色值 | 题解 | 正向（从入度为0的节点开始）DFS用记忆化搜索，逆向（以出度的节点为终点）是DP |
| 题解 |
数组元素作为状态参数
把状态定义为与元素直接相关，与其索引 位置无关。通常需要根据元素（因为状态直接与元素相关）去查找，可能会用到二分（如果有序）。状态的长度也与原数组长度无关。一般用列表或者Map来存储状态。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 300. 最长递增子序列 | 题解 | |
| 354. 俄罗斯套娃信封问题 | 题解 | |
| 1218. 最长定差子序列 | 题解 | 用Map存储状态 |
| 题解 | ||
| 题解 | ||
| 题解 |
增加维度，寻找隐藏参数
有些题目，光靠给出的数组元素无法确定状态转移方程，比如直接使用位置（索引）或者元素都无法直接确定状态，这时就需要引入更多的参数，这个参数可能是由相关元素计算而来的。这就是状态方程的隐藏参数，需要把它挖掘出来作为新参数，这就升维。典型题目就是题1027，子序列需要两个参数，一个是队尾，也就是当前元素nums[i]，但光有当前元素无法找到子序列的前一个元素，因为公差不确定。这个时候就需要升维，把公差也当作一个参数，向前面枚举寻找前一个元素nums[j]时，这时公差就有了，就是nums[i]-nums[j]，这样通过两个参数就能确定状态转移方程。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 1027. 最长等差数列 | 题解 | |
| 题解 | ||
| 题解 |
参考资料
- Dynamic Programming
- Understanding Dynamic Programming
- Dynamic Programming
- Demystifying Dynamic Programming
- Dynamic Programming
- Dynamic Programming
- 动态规划部分
- 看一遍就理解：动态规划详解
- 五大基本算法之动态规划算法 DP dynamic programming
- 一文搞定动态规划问题（附DP所有问题链接）
- 什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
- 动态规划一篇就够了 全网第二详细, 逐步理解, 万字总结
- 算法-动态规划 Dynamic Programming–从菜鸟到老鸟
- Optimal Substructure Property
- Optimal substructure in Dynamic Programing
- Optimal Substructure and Overlapping Subproblems
- 动态规划答疑篇
- 动态规划的最优子结构问题，有什么样的问题它不满足最优子结构？
- 深入浅出理解动态规划（二） | 最优子结构
- 动态规划（最优子结构、重叠子问题）——附代码示例
- Overlapping Subproblems Property in Dynamic Programming | DP-1
- Optimal Substructure Property in Dynamic Programming | DP-2
- What are overlapping subproblems in Dynamic Programming (DP)?