动态规划(Dynamic Programming)动态规划是用来求解具有最优子结构性质问题的一种方法。通俗的来说如果一个问题可以分成多个子问题或者分成多个步骤，每个子问题有多个解或者每个步骤有多个选择，最终求整体问题的一个最优解（最大值，最小值，方法总数，是否可行等等），这样的问题就适合用动态规划来求解。
动态规划一般可分为自顶而下式和自下而上式，自顶而下是通过递归，但因为涉及大量重复计算而导致时间复杂度过高，所以一般都是采用自下而上式，借助额外的空间来缓存子问题的解，减少重复计算从而降低时间复杂度，与记忆化搜索有点类似。
动态规划的适用范围
最优子结构性质
最优子结构特性（Optimal Substructure）是指一个问题可以分成多个子问题，每个问题的最优解凑成整个问题的最优解。
重叠子问题性质
重叠子问题(Overlapping subproblems)是指一个问题可以分成多个子问题，每个子问题的解会重复使用多次，也就说后一个子问题的解需要使用到前一个子问题的解。最为典型的就是Fibonacci数列，也就是常说的自上而下的方式来实现动态规划（递归式），因为子问题重复，所以为了提升效率必须把子问题的解存储下来以防止重复计算。
寻找状态转移方程
动态规划并不像排序或者二分查找那样有具体的形式，它更是一种策略而非具体的算法，发现一个题目可以用动态规划求解时，还远远不够，要想写出代码，必须推导出来状态转移方程，这才是动态规划的核心，而动态如何定义，又如何转移要视具体的问题而定变化万千，所以说动态规划是最难的一类题，没有之一。
一般而言状态转移方程要以结果为导向，也就是说用这个方程能得到问题的解，这依然是一句废话，要通过大量的练习才能掌握。比如像经典的打家劫舍，f(i)为到第i个房子时所能获得的最大价值，f(n)通常为问题的解。
有些时候，不能直接得到问题的解，而是要再在状态方程f(i)之外，再叠加一个全局最优解（如全局最大值，最小值），通常子串子序列的问题都是此类，状态f(i)定义为到i时的最长子串或者子序列，但f(n-1)并不是全局的最优解，这时再在状态基础之上求个全局最优解就可以了，如最长有效括号。
动态规划的分类总结
动态规划问题博大深精，甚至有人说万物皆可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. 最少侧跳次数 | 题解 | 典型一维多状态，与粉刷房子类似 |
| 题解 | ||
| 题解 | ||
| 题解 |
一维二次
输入是一维，但是时间复杂度会上升到O(n2)。原因在于当前的状态f(i)与其前面的所有状态都有可能有关系，通常f(i)是前面状态的一种极值，或者累加。状态转移方向一般为f(i) = max{f(j), 0<=j<i}。因为对于每一个状态，都要遍历一次其前面的所有状态，以寻找满足某种约束条件的结果，所以时间复度会上升到O(n2)。典型的问题是背包问题和子序列问题。
背包问题是典型的一维二次问题，关于背包问题，单独总结了一篇文章。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 45. 跳跃游戏 II | 题解 | |
| 55. 跳跃游戏 | 题解 | |
| 300. 最长递增子序列 | 题解 | |
| 343. 整数拆分 | 题解 | |
| 376. 摆动序列 | 题解 | |
| 673. 最长递增子序列的个数 | 题解 | |
| 873. 最长的斐波那契子序列的长度 | 题解 | |
| 1388. 3n 块披萨 | 题解 | |
| 题解 |
一维二次叠加缓存优化
某些一维二次，就是当前状态与其前面的所有状态都可能相关，但是否相关的判断并不是O(1)的，通常需要借助缓存来防止重复计算以降到O(1)。最为典型的就是字符串回文类的问题，以及字符串分割类的问题。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 132. 分割回文串 II | 题解 | |
| 题解 | ||
| 题解 |
双一维二次
输入是两个一维数组（或者序列或者字符串），因为输入是两个一维的，必然是要按个遍历一次，所以时间复杂度不可能小于二次（O(mn)），其中m和n是两个一维数组的和度。通常空间复杂度都有优化到一维。最为典型的例子就是两个字符串的最长公共子序列。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 10. 正则表达式匹配 | 题解 | |
| 72. 编辑距离 | 题解 | |
| 392. 判断子序列 | 题解 | |
| 516. 最长回文子序列 | 题解 | |
| 583. 两个字符串的删除操作 | 题解 | |
| 1143. 最长公共子序列 | 题解 | |
| 题解 | ||
| 题解 |
二维二次
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 剑指 Offer 47. 礼物的最大价值 | 题解 | |
| 62. 不同路径 | 题解 | |
| 64. 最小路径和 | 题解 | |
| 120. 三角形最小路径和 | 题解 | |
| 174. 地下城游戏 | 题解 | 与常规方向相反 |
| 221. 最大正方形 | 题解 | |
| 799. 香槟塔 | 题解 | |
| 题解 | ||
| 题解 |
区间DP
这是比较难的一类DP，状态是由一个区间约束。前面的DP的状态都是由一个位置来约束，通常定义一个f(i)就可以，即使是二维列表，每个列表也只由一个位置来决定状态。但区间问题必须 由一个区间来决定状态，单靠一个位置无法确定它的状态。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 5. 最长回文子串 | 题解 | |
| 87. 扰乱字符串 | 题解 | |
| 312. 戳气球 | 题解 | 区间DP，二维状态 |
| 题解 | ||
| 题解 |
树形DP
通常DP涉及的数据结构都是线性的数组或者字符串，或者二维的矩阵。但也有其他的数据结构，树形DP是指以树（通常是二叉树）为数据结构的DP算法。
因为树的遍历只能是从根开始，先父节点再子节点，因此DP的状态转移方程只能从父节点递推而来。通常涉及两个状态，再叠加一些约束条件，约束条件都是父节点与子节点之间的约束条件。
再有就是，树形DP的递推过程并不是线性的，无法用常规的数组来保存状态。状态一般都是跟节点绑定的，所以最常用的方式是用哈希表来存储状态，以节点为键值，值为节点对应的状态，保存在哈希表中。如果是两个状态，则需要两个哈希表。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 337. 打家劫舍 III | 题解 | |
| 1372. 二叉树中的最长交错路径 | 题解 | |
| 题解 | ||
| 题解 |
参考资料
- 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)?