AI summary
type
status
date
slug
summary
category
tags
icon
password
细节问题
很多读者对动态规划问题的 base case、备忘录初始值等问题存在疑问，本文就专门讲一讲这类问题，顺便聊一聊怎么通过题目的蛛丝马迹揣测出题人的小心思，辅助我们解题。
931. 下降路径最小和
给你一个n x n的 方形 整数数组matrix，请你找出并返回通过matrix的下降路径 的 最小和 。下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置(row, col)的下一个元素应当是(row + 1, col - 1)、(row + 1, col)或者(row + 1, col + 1)。
我们可以定义一个
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) 的最小路径和。当然，上述代码是暴力穷举解法，我们可以用备忘录的方法消除重叠子问题，完整代码如下：
- base case 的条件如何确定？
首先，说说 base case 为什么是
i == 0，返回值为什么是 matrix[0][j]，这是根据 dp 函数的定义所决定的。回顾我们的
dp 函数定义：从第一行（
matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)。根据这个定义，我们就是从
matrix[0][j] 开始下落。那如果我们想落到的目的地就是 i == 0，所需的路径和当然就是 matrix[0][j] 呗。- 备忘录初始值如何确定？
再说说备忘录
memo 的初始值为什么是 66666，这是由题目给出的数据范围决定的。备忘录
memo 数组的作用是什么？就是防止重复计算，将
dp(matrix, i, j) 的计算结果存进 memo[i][j]，遇到重复计算可以直接返回。那么，我们必须要知道
memo[i][j] 到底存储计算结果没有，对吧？如果存结果了，就直接返回；没存，就去递归计算。所以，
memo 的初始值一定得是特殊值，和合法的答案有所区分。我们回过头看看题目给出的数据范围：
matrix 是 n x n 的二维数组，其中 1 <= n <= 100；对于二维数组中的元素，有 -100 <= matrix[i][j] <= 100。
假设
matrix 的大小是 100 x 100，所有元素都是 100，那么从第一行往下落，得到的路径和就是 100 x 100 = 10000，也就是最大的合法答案。类似的，依然假设
matrix 的大小是 100 x 100，所有元素是 -100，那么从第一行往下落，就得到了最小的合法答案 -100 x 100 = -10000。也就是说，这个问题的合法结果会落在区间
[-10000, 10000] 中。所以，我们
memo 的初始值就要避开区间 [-10000, 10000]，换句话说，memo 的初始值只要在区间 (-inf, -10001] U [10001, +inf) 中就可以。- 边界情况返回值如何确定？
最后，说说对于不合法的索引，返回值应该如何确定，这需要根据我们状态转移方程的逻辑确定。
因为我们调用的是
min 函数，最终返回的值是最小值，所以对于不合法的索引，只要 dp 函数返回一个永远不会被取到的最大值即可。刚才说了，合法答案的区间是
[-10000, 10000]，所以我们的返回值只要大于 10000 就相当于一个永不会取到的最大值。换句话说，只要返回区间
[10001, +inf) 中的一个值，就能保证不会被取到。至此，我们就把动态规划相关的三个细节问题举例说明了。
- 拓展延伸一下，建议大家做题时，除了题意本身，一定不要忽视题目给定的其他信息。
本文举的例子，测试用例数据范围可以确定「什么是特殊值」，从而帮助我们将思路转化成代码。
除此之外，数据范围还可以帮我们估算算法的时间/空间复杂度。
比如说，有的算法题，你只想到一个暴力求解思路，时间复杂度比较高。如果发现题目给定的数据量比较大，那么肯定可以说明这个求解思路有问题或者存在优化的空间。
除了数据范围，有时候题目还会限制我们算法的时间复杂度，这种信息其实也暗示着一些东西。
比如要求我们的算法复杂度是 O(NlogN)，你想想怎么才能搞出一个对数级别的复杂度呢？
肯定得用到 二分搜索 或者二叉树相关的数据结构，比如
TreeMap，PriorityQueue 之类的对吧。再比如，有时候题目要求你的算法时间复杂度是 O(MN)，这可以联想到什么？
可以大胆猜测，常规解法是用 回溯算法 暴力穷举，但是更好的解法是动态规划，而且是一个二维动态规划，需要一个
M * N 的二维 dp 数组，所以产生了这样一个时间复杂度。如果你没啥解题思路，那有了这些推测之后，最起码可以给你的思路一些方向吧？
总之，多动脑筋，不放过任何蛛丝马迹，刷题小能手就是你。
穷举的两种视角
就算
dp 函数/数组的定义相同，如果你使用不同的「视角」进行穷举，效率也不见得是相同的。关于穷举「视角」的问题，前文 球盒模型：回溯算法穷举的两种视角 讲了回溯算法中不同的穷举视角导致的不同解法，其实这种视角的切换在动态规划类型问题中依然存在。前文对排列的举例非常有助于你理解穷举视角的问题。
115. 不同的子序列
给你两个字符串s和t，统计并返回在s的 子序列 中t出现的个数，结果需要对 10^9 + 7 取模。
你要数一数
s 的子序列中有多少个 t，说白了就是穷举嘛，那么首先想到的就是能不能把原问题分解成规模更小的子问题，然后通过子问题的答案推导出原问题的答案。首先，我们可以这样定义一个
dp 函数：s[i..] 的子序列中 t[j..] 出现的次数为 dp(s, i, t, j)这道题对
dp 函数的定义很简单直接，题目让你求出现次数，那你就定义函数返回值为出现次数就可以。有了这个
dp 函数，题目想要的结果是 dp(s, 0, t, 0)，base case 也很容易写出来，解法框架如下：回顾一下之前讲的排列组合的「球盒模型」，这里是不是很类似？
t 中的若干字符就好像若干盒子，s 中的若干字符就好像若干小球，你需要做的就是给所有盒子都装一个小球。所以这里就有两种穷举思路了，分别是站在 t 的视角（盒子选择小球）和站在 s 的视角（小球选择盒子）。- 从 t 的视角穷举
我们的原问题是求
s[0..] 的所有子序列中 t[0..] 出现的次数，那么可以先看 t[0] 在 s 中的什么位置，假设 s[2], s[6] 是字符 t[0]，那么原问题转化成了在 s[3..] 和 s[7..] 的所有子序列中计算 t[1..] 出现的次数。翻译成代码大致就是这个思路：
这道题就解决了，不过效率不算很高，我们可以粗略估算一下这个算法的时间复杂度上界，其中
M, N 分别代表 s, t 的长度，算法的「状态」就是 dp 函数参数 i, j 的组合：。主要高在哪里呢？对「状态」的穷举已经有了
memo 备忘录的优化，所以 O(MN) 的复杂度是必不可少的，关键问题出在 dp 函数中的 for 循环。是否可以优化掉
dp 函数中的 for 循环呢？可以的，这就需要另一种穷举视角来解决这个问题。- 从 s 的视角穷举
我们的原问题是计算
s[0..] 的所有子序列中 t[0..] 出现的次数，可以先看看 s[0] 是否能匹配 t[0]，如果不匹配，那没得说，原问题就可以转化为计算 s[1..] 的所有子序列中 t[0..] 出现的次数；但如果
s[0] 可以匹配 t[0]，那么又有两种情况，这两种情况是累加的关系：- 让
s[0]匹配t[0]，那么原问题转化为在s[1..]的所有子序列中计算t[1..]出现的次数。
- 不让
s[0]匹配t[0]，那么原问题转化为在s[1..]的所有子序列中计算t[0..]出现的次数。
为啥明明
s[0] 可以匹配 t[0]，还不让它俩匹配呢？主要是为了给 s[0] 之后的元素匹配的机会，比如 s = "aab", t = "ab"，就有两种匹配方式：a_b 和 _ab。把以上思路写成状态转移方程：
完整代码如下：
这个解法中
dp 函数递归的次数，即状态 i, j 的不同组合的个数为 O(MN)，而 dp 函数本身没有 for 循环，即时间复杂度为 O(1)，所以算法总的时间复杂度就是 O(MN)，比刚才的解法要好一些，你提交这个解法代码，耗时明显比刚才的解法少一些。空间压缩
动态规划算法的主要表现形式是带备忘录的递归解法，或者递推的迭代解法，这两种解法本质上都是一样的，效率也差不多。
本文将介绍动态规划迭代写法的一个优势，就是可以将
dp 数组进行空间压缩（一般称为滚动数组技巧），降低空间复杂度。简单说就是，某些情况下状态转移方程仅依赖于相邻的状态，那么就没必要维护整个
dp 数组，仅维护所需的几个状态即可，这样可以降低空间复杂度。能够使用空间压缩技巧的动态规划一般都是二维
dp 问题，你看它的状态转移方程，如果计算状态 dp[i][j] 需要的都是 dp[i][j] 相邻的状态，那么就可以使用空间压缩技巧，将二维的 dp 数组转化成一维，将空间复杂度从 O(N^2) 降低到 O(N)。什么叫「和
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] 呢？回想上面的图，「投影」其实就是把多行变成一行，所以想把二维
dp 数组压缩成一维，一般来说是把第一个维度，也就是 i 这个维度去掉，只剩下 j 这个维度。压缩后的一维 dp 数组就是之前二维 dp 数组的 dp[i][..] 那一行。我们先将上述代码进行改造，直接无脑去掉
i 这个维度，把 dp 数组变成一维：上述代码的一维
dp 数组只能表示二维 dp 数组的一行 dp[i][..]。但是我们想得到 dp[i+1][j-1], dp[i][j-1], dp[i+1][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] 的位置。那么问题已经解决了一大半了，只剩下二维
dp 数组中的 dp[i+1][j-1] 这个状态我们不能直接从一维 dp 数组中得到。如果我们想得到
dp[i+1][j-1]，就必须在它被覆盖之前用一个临时变量 temp 把它存起来，并把这个变量的值保留到计算 dp[i][j] 的时候。为了达到这个目的，结合上图，我们可以这样写代码：如何把 base case 也打成一维呢？很简单，记住空间压缩就是投影，我们把 base case 投影到一维看看：
二维
dp 数组中的 base case 全都落入了一维 dp 数组，不存在冲突和覆盖。所以完整代码如下：
其他问题
最优子结构
「最优子结构」是某些问题的一种特定性质，并不是动态规划问题专有的。也就是说，很多问题其实都具有最优子结构，只是其中大部分不具有重叠子问题，所以我们不把它们归为动态规划系列问题而已。
我先举个很容易理解的例子：假设你们学校有 10 个班，你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩，你会不会算？当然会，而且你不用重新遍历全校学生的分数进行比较，而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。
我给你提出的这个问题就符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。
你看，这么简单的问题都有最优子结构性质，只是因为显然没有重叠子问题，所以我们简单地求最值肯定用不出动态规划。
再举个例子：假设你们学校有 10 个班，你已知每个班的最大分数差（最高分和最低分的差值）。那么现在我让你计算全校学生中的最大分数差，你会不会算？可以想办法算，但是肯定不能通过已知的这 10 个班的最大分数差推到出来。因为这 10 个班的最大分数差不一定就包含全校学生的最大分数差，比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差。
这次我给你提出的问题就不符合最优子结构，因为你没办通过每个班的最优值推出全校的最优值，没办法通过子问题的最优值推出规模更大的问题的最优值。前文说过，想满足最优子结，子问题之间必须互相独立。全校的最大分数差可能出现在两个班之间，显然子问题不独立，所以这个问题本身不符合最优子结构。
重叠子问题
首先，最简单粗暴的方式就是画图，把递归树画出来，看看有没有重复的节点。
比如最简单的例子，斐波那契数列的递归树：
这棵递归树很明显存在重复的节点，所以我们可以通过备忘录避免冗余计算。
但毕竟斐波那契数列问题太简单了，实际的动态规划问题比较复杂，比如二维甚至三维的动态规划，当然也可以画递归树，但不免有些复杂。
但稍加思考就可以知道，其实根本没必要画图，可以通过递归框架直接判断是否存在重叠子问题。
具体操作就是直接删掉代码细节，抽象出该解法的递归框架：
可以看到
i, j 的值在不断减小，那么我问你一个问题：如果我想从状态 (i, j) 转移到 (i-1, j-1)，有几种路径？显然有两种路径，可以是
(i, j) -> #1 -> #2 或者 (i, j) -> #2 -> #1，不止一种，说明 (i-1, j-1) 会被多次计算，所以一定存在重叠子问题。dp 数组大小设置
比如说后文 编辑距离问题，我首先讲的是自顶向下的递归解法，实现了这样一个
dp 函数：然后改造成了自底向上的迭代解法：
这两种解法思路是完全相同的，但就有读者提问，为什么迭代解法中的
dp 数组初始化大小要设置为 int[m+1][n+1]？为什么 s1[0..i] 和 s2[0..j] 的最小编辑距离要存储在 dp[i+1][j+1] 中，有一位索引偏移？能不能模仿
dp 函数的定义，把 dp 数组初始化为 int[m][n]，然后让 s1[0..i] 和 s2[0..j] 的最小编辑距离要存储在 dp[i][j] 中？理论上，你怎么定义都可以，只要根据定义处理好 base case 就可以。
你看
dp 函数的定义，dp(s1, i, s2, j) 计算 s1[0..i] 和 s2[0..j] 的编辑距离，那么 i, j 等于 -1 时代表空串的 base case，所以函数开头处理了这两种特殊情况。再看
dp 数组，你当然也可以定义 dp[i][j] 存储 s1[0..i] 和 s2[0..j] 的编辑距离，但问题是 base case 怎么搞？索引怎么能是 -1 呢？dp 数组遍历方向
我相信读者做动态规问题时，肯定会对
dp 数组的遍历顺序有些头疼。我们拿二维 dp 数组来举例，有时候我们是正向遍历：有时候我们反向遍历：
有时候可能会斜向遍历：
甚至更让人迷惑的是，有时候发现正向反向遍历都可以得到正确答案，比如我们在 团灭股票问题 中有的地方就正反皆可。
如果仔细观察的话可以发现其中的原因，你只要把住两点就行了：
- 遍历的过程中，所需的状态必须是已经计算出来的。
- 遍历结束后，存储结果的那个位置必须已经被计算出来。
下面来具体解释上面两个原则是什么意思。
比如 编辑距离 这个经典的问题，我们通过对
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 数组？肯定是正向遍历。再举一例，回文子序列问题，我们通过过对
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 和最终结果的存储位置，保证遍历过程中使用的数据都是计算完毕的就行，有时候确实存在多种方法可以得到正确答案，可根据个人口味自行选择。