动态规划问题的一般形式就是求最值，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。
- 动态规划穷举的特点：存在「重叠子问题」
- 动态规划问题一定会具备：「最优子结构」
- 难点：列出正确的「状态转移方程」才能正确地穷举
- 思维框架，辅助思考状态转移方程：明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。
斐波那契数列 —— 设计重叠子问题
1. 暴力递归
斐波那契数列的数学形式就是递归的，写成代码就是这样：
递归树:
- 递归算法的时间复杂度: O(2^n) * O(1)
这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。
2. 带备忘录的递归解法：自顶向下
一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典）
<br />递归树，你就知道「备忘录」到底做了什么：
时间复杂度：O(n)*O(1)
实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
至此，带备忘录的递归解法的效率已经和迭代的动态规划一样了。实际上，这种解法和迭代的动态规划思想已经差不多，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」
3. dp数组的迭代算法：自底向上
有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算。
- 画个图就很好理解了，而且你发现这个 DP table 特别像之前那个「剪枝」后的结果，只是反过来算而已。实际上，带备忘录的递归解法中的「备忘录」，最终完成后就是这个 DP table，所以说这两种解法其实是差不多的，大部分情况下，效率也基本相同。
这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：
千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者 DP table，再无奥妙可言。
优化细节
当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：
凑零钱 —— 涉及 最优子结构
1. 暴力递归
- 首先，这是动态规划问题，因为具有「最优子结构」。要符合「最优子结构」，子问题间必须互相独立。
什么是 最优子结构 呢？
「最优子结构」是某些问题的一种特定性质，并不是动态规划问题专有的。也就是说，很多问题其实都具有最优子结构，只是其中大部分不具有重叠子问题，所以我们不把它们归为动态规划系列问题而已。
- 但最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的，以后碰到那种恶心人的最值题，思路往动态规划想就对了，这就是套路。
- 找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。这也是套路，经常刷题的朋友应该能体会。
遇到最优子结构失效情况，怎么办？策略是：改造问题。
- 为什么说它符合最优子结构呢？
- 比如你想求amount = 11时的最少硬币数（原问题），如果你知道凑出amount = 10的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案，因为硬币的数量是没有限制的，子问题之间没有相互制约，是互相独立的。
- 那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程。
- 先确定「状态」，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额amount。
- 然后确定dp函数的定义：函数 dp(n)表示，当前的目标金额是n，至少需要dp(n)个硬币凑出该金额。
然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态。具体到这个问题，无论当的目标金额是多少，选择就是从面额列表coins中选择一个硬币，然后目标金额就会减少：
最后明确 base case，显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时无解，返回 -1：
<br />至此，状态转移方程其实已经完成了，以上算法已经是暴力解法了，以上代码的数学形式就是状态转移方程：<br />
需要消除一下重叠子问题，比如amount = 11, coins = {1,2,5}时画出递归树看看：
时间复杂度分析： O(k * n^k)，指数级别。
2. 带备忘录的递归解法：自顶向下
- 总的时间复杂度是 O(kn)
3. dp数组的迭代算法：自底向上
也可以自底向上使用 dp table 来消除重叠子问题，dp数组的定义和刚才dp函数类似，定义也是一样的：
dp[i] = x表示，当目标金额为i时，至少需要x枚硬币。
PS：为啥dp数组初始化为amount + 1呢，因为凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币），所以初始化为amount + 1就相当于初始化为正无穷，便于后续取最小值。
总结
- 第一个斐波那契数列的问题
- 解释了如何通过「备忘录」或者「dp table」的方法来优化递归树，
- 并且明确了这两种方法本质上是一样的，只是自顶向下和自底向上的不同而已。
- 第二个凑零钱的问题
- 展示了如何流程化确定「状态转移方程」，只要通过状态转移方程写出暴力递归解，剩下的也就是优化递归树，消除重叠子问题而已。
- 列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
- 备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门
dp数组的遍历方向
- 正序遍历
- 反序遍历
- 斜向遍历
有时发现正反向遍历都可以得到正确答案，比如 团灭 LeetCode 股票买卖问题 中有的地方就正反皆可。
那么，如果仔细观察的话可以发现其中的原因的。你只要把住两点就行了：
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置。
编辑距离
- 通过对dp数组的定义，确定了 base case 是dp[..][0]和dp[0][..]，最终答案是dp[m][n]；
- 而且我们通过状态转移方程知道dp[i][j]需要从dp[i-1][j],dp[i][j-1],dp[i-1][j-1]转移而来，如下图：
那么，参考刚才说的两条原则，你该怎么遍历dp数组？肯定是正向遍历：
- 因为，这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的，而且最终结束在我们想要的答案dp[m][n]。
最长回文子序列
- 通过过对dp数组的定义，确定了 base case 处在中间的对角线，
- dp[i][j]需要从dp[i+1][j],dp[i][j-1],dp[i+1][j-1]转移而来，想要求的最终答案是dp[0][n-1]，如下图：
这种情况根据刚才的两个原则，就可以有两种正确的遍历方式：
- 要么从左至右斜着遍历，要么从下向上从左到右遍历，这样才能保证每次dp[i][j]的左边、下边、左下边已经计算完毕，最终得到正确结果。
现在，你应该理解了这两个原则，主要就是看 base case 和最终结果的存储位置，保证遍历过程中使用的数据都是计算完毕的就行，有时候确实存在多种方法可以得到正确答案，可根据个人口味自行选择。
base case 和 备忘录的初始值 怎么定？
讲一讲动态规划问题的 base case、备忘录初始值， 顺便聊一聊怎么通过题目的蛛丝马迹揣测出题人的小心思，辅助我们解题。
下降路径最小和
借这道题来讲讲 base case 的返回值、备忘录的初始值、索引越界情况的返回值如何确定
1. 通过 动态规划的标准套路 介绍一下这道题的解题思路
- 定义一个dp数组 int dp(int[][] matrix, int i, int j);
- dp函数的含义：从第一行（matrix[0][..]）向下落，落到位置matrix[i][j]的最小路径和为dp(matrix, i, j)。
- dp函数怎么实现
对于matrix[i][j]，只有可能从matrix[i-1][j], matrix[i-1][j-1], matrix[i-1][j+1]这三个位置转移过来。
那么，只要知道到达(i-1, j), (i-1, j-1), (i-1, j+1)这三个位置的最小路径和，加上matrix[i][j]的值，就能够计算出来到达位置(i, j)的最小路径和：
上述代码是暴力穷举解法，我们可以用备忘录的方法消除重叠子问题，完整代码如下：
2. 对于这个dp函数仔细探讨三个问题：
1、对于索引的合法性检测，返回值为什么是 99999？其他的值行不行？
2、base case 为什么是i == 0？
3、备忘录memo的初始值为什么是 66666？其他值行不行？
揣摩
- 测试用例数据范围可以确定「什么是特殊值」，从而帮助我们将思路转化成代码。
- 除此之外，数据范围还可以帮我们估算算法的时间/空间复杂度。
比如说，有的算法题，你只想到一个暴力求解思路，时间复杂度比较高。如果发现题目给定的数据量比较大，那么肯定可以说明这个求解思路有问题或者存在优化的空间。
- 除了数据范围，有时候题目还会限制我们算法的时间复杂度，这种信息其实也暗示着一些东西。
状态压缩技巧：动态规划的降维打击
上文 动态规划技巧对算法效率的提升非常可观：一般都能把指数级和阶乘级 时间复杂度 优化成 O(N^2)
- 但是，动态规划本身也是可以进行阶段性优化的：比如说我们常听说的「状态压缩」技巧，就能够把很多动态规划解法的空间复杂度进一步降低，由 O(N^2) 降低到 O(N)。
- 能使用状态压缩技巧的动态规划都是二维dp问题。你看它的状态转移方程，如果计算状态dp[i][j]需要的都是dp[i][j]相邻的状态，那么就可以使用状态压缩技巧，将二维的dp数组转化成一维，将空间复杂度从 O(N^2) 降低到 O(N)。
不探讨如何推状态转移方程，只探讨对二维 DP 问题进行状态压缩的技巧。
- 能够使用状态压缩技巧的动态规划都是二维dp问题 ( 它的状态转移方程，如果计算状态dp[i][j]需要的都是dp[i][j]相邻的状态，那么就可以使用状态压缩技巧 )
「最长回文子序列」
对dp[i][j]的更新，其实只依赖于dp[i+1][j-1], dp[i][j-1], dp[i+1][j]这三个状态：
- 这就叫和dp[i][j]相邻。反正计算dp[i][j]只需要这三个相邻状态，根本不需要那么大一个二维的 dp table
状态压缩的核心思路就是，将二维数组「投影」到一维数组：
状态压缩的难点：思路很直观，但有一个明显的问题：图中dp[i][j-1]和dp[i+1][j-1]这两个状态处在同一列，而一维数组中只能容下一个，那么计算dp[i][j]时，他俩必然有一个会被另一个覆盖，怎么办？
解决压缩存在的覆盖问题
算法优化的过程
- 先写出可读性很好的暴力递归算法
- 然后尝试运用动态规划技巧优化重叠子问题
- 最后尝试用状态压缩技巧优化空间复杂度。 O(N^2) 降低到 O(N)
- 运用我们前文 动态规划框架套路详解 的套路找出状态转移方程，写出一个正确的动态规划解法，然后才有可能观察状态转移的情况，分析是否可能使用状态压缩技巧来优化。
- 未进行 压缩 前 状态转移方程 的代码
- 二维 —> 一维
- 一般来说是把第一个维度（也就是 i 这个维度）去掉，只剩下j这个维度。压缩后的一维dp数组就是之前二维dp数组的dp[i][..]那一行。
1）我们先将上述代码进行改造，直接无脑去掉i这个维度，把dp数组变成一维：
上述代码的一维dp数组只能表示二维dp数组的一行dp[i][..]，那我怎么才能得到dp[i+1][j-1], dp[i][j-1], dp[i+1][j]这几个必要的的值，进行状态转移呢？
2）代码中注释的位置，将要进行状态转移，更新dp[j]，那么我们要来思考两个问题：
- 在对dp[j]赋新值之前，dp[j]对应着二维dp数组中的什么位置？
dp[j-1]对应着二维dp数组中的什么位置?
问题 1，在对dp[j]赋新值之前，dp[j]的值就是外层 for 循环上一次迭代算出来的值，也就是对应二维dp数组中dp[i+1][j]的位置。 问题 2，dp[j-1]的值就是内层 for 循环上一次迭代算出来的值，也就是对应二维dp数组中dp[i][j-1]的位置。 (直接在上上图中max()对应上图中的max()
那问题已解决一大半，只剩二维dp数组中的dp[i+1][j-1]这个状态（s[i]==s[j]的情况）我们不能直接从一维dp数组中得到:
- 因为 for 循环遍历i和j的顺序为从左向右，从下向上。所以可以发现，在更新一维dp数组的时候，dp[i+1][j-1]会被dp[i][j-1]覆盖掉，图中标出了这四个位置被遍历到的次序：（这个图最好把有颜色的方块都往上移动一格，方便理解）
解决：那么如果我们想得到dp[i+1][j-1]，就必须在它被覆盖之前用一个临时变量temp把它存起来，并把这个变量的值保留到计算dp[i][j]的时候。为了达到这个目的，结合上图，我们可以这样写代码：
用具体的数值来拆解这个逻辑：假设现在i = 5, j = 7且s[5] == s[7]，那么现在会进入下面这个逻辑对吧：
- pre变量是什么？是内层 for 循环上一次迭代的temp值。
- 内层 for 循环上一次迭代的temp值是什么？是dp[j-1]也就是dp[6]，但这是外层 for 循环上一次迭代对应的dp[6]，也就是二维dp数组中的dp[i+1][6] = dp[6][6]。
也就是说，pre变量就是dp[i+1][j-1] = dp[6][6]，也就是我们想要的结果。
3) base case
回溯 vs 动态规划
用力扣第 494 题「目标和」来详细对比一下回溯算法和动态规划：
- 注意，给出的例子 nums 全是 1，但实际上可以是任意正整数哦。
- 如何发现重叠子问题？看是否可能出现重复的「状态」。
- 如何一眼看出重叠子问题的方法？
回溯
消除重叠子问题
消除重叠子问题之后，算法的时间复杂度是多少？其实最坏情况下依然是 O(2^N)。
- 为什么呢？因为我们只不过恰好发现了重叠子问题，顺手用备忘录技巧给优化了，但是底层思路没有变，依然是暴力穷举的回溯算法，依然在遍历一棵二叉树。这只能叫对回溯算法进行了「剪枝」，提升了算法在某些情况下的效率，但算不上质的飞跃。
动态规划
子集问题
背包问题
- 压缩空间
注意是怎么引入二维dp数组
若有收获，就点个赞吧
0 人点赞
