子序列问题 | LianoのBlog

AI summary

type

status

date

slug

summary

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

解决两个字符串的动态规划问题，一般都是用两个指针 i, j 分别指向两个字符串的头部或尾部，然后尝试写状态转移方程。

比方说让 i, j 分别指向两个字符串的尾部，把 dp[i], dp[j] 定义为 s1[0..i], s2[0..j] 子串的编辑距离，那么 i, j 一步步往前移动的过程，就是问题规模（子串长度）逐步减小的过程。

base case 为其中一个字符串为空时，最小操作数为另一个字符串的长度，dp[i][j] 表示 s1[0:i] 和 s2[0:j] 的最小编辑距离，先看下暴力递归解法：

然后可以很简单地加个备忘录来优化复杂度：

然后是自底向上的 dp 解法，dp[..][0] 和 dp[0][..] 对应 base case，dp[i][j] 的含义和 dp 函数一致。

有一个细节，既然每个状态只和它附近的三个状态有关，空间复杂度是可以压缩成 O(min(M,N)) 的。但是可解释性大大降低，读者可以自己尝试优化一下。

你可能还会问，这里只求出了最小的编辑距离，那具体的操作是什么？

这个其实很简单，代码稍加修改，给 dp 数组增加额外的信息，最后倒推即可。

最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

滑动窗口

其实第一次看到这道题，我首先想到的是滑动窗口算法，因为滑动窗口算法就是专门处理子串/子数组问题的，这里不就是子数组问题么？

前文 滑动窗口算法框架详解 中讲过，想用滑动窗口算法，先问自己几个问题：

什么时候应该扩大窗口？

什么时候应该缩小窗口？

什么时候更新答案？

我之前认为这题用不了滑动窗口算法，理由是在包含负数的条件下对 nums 求和，应该无法确定什么时候扩大和缩小窗口。但经读者评论的启发，我发现这道题确实是可以用滑动窗口技巧解决，不过有些 case 有点过于精巧，确实不容易想到。

我们可以在窗口内元素之和大于等于 0 时扩大窗口，在窗口内元素之和小于 0 时缩小窗口，在每次移动窗口时更新答案。

正确性解释：
先讨论一种特殊情况，就是 nums 中全是负数的时候，此时算法是可以得到正确答案的。
接下来讨论一般情况，nums 中有正有负，这种情况下元素和最大的那个子数组一定是以正数开头的（以负数开头的话，把这个负数去掉，就可以得到和更大的子数组了，与假设相矛盾）。那么此时我们需要穷举所有以正数开头的子数组，计算他们的元素和，找到元素和最大的那个子数组。
说到这里，解法代码的逻辑应该就清晰了。算法只有在窗口元素和大于 0 时才会不断扩大窗口，并且在扩大窗口时更新答案，这其实就是在穷举所有正数开头的子数组，寻找子数组和最大的那个，所以这段代码能够得到正确的结果。

动态规划

下面还是进入正题，介绍一下常规的动态规划解法。

对于这类子数组问题，我们就要重新定义 dp 数组的含义：

以 nums[i] 为结尾的「最大子数组和」为 dp[i]。

这种定义之下，想得到整个 nums 数组的「最大子数组和」，需要遍历整个 dp 数组。

dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。

代码如下：

前缀和

回顾一下，前缀和数组 preSum 就是 nums 元素的累加和，preSum[i+1] - preSum[j] 其实就是子数组 nums[j..i] 之和（根据 preSum 数组的实现，索引 0 是占位符，所以 i 有一位索引偏移）。

那么反过来想，以 nums[i] 为结尾的最大子数组之和是多少？其实就是 preSum[i+1] - min(preSum[0..i])。

所以，我们可以利用前缀和数组计算以每个元素结尾的子数组之和，进而得到和最大的子数组。直接看前缀和的解法代码吧：

最长公共子序列

不知道大家做算法题有什么感觉，我总结出来做算法题的技巧就是，把大的问题细化到一个点，先研究在这个小的点上如何解决问题，然后再通过递归/迭代的方式扩展到整个问题。

比如说我们前文解决二叉树的题目，我们就会把整个问题细化到某一个节点上，想象自己站在某个节点上，需要做什么，然后套二叉树递归框架就行了。

动态规划系列问题也是一样，尤其是子序列相关的问题。本文从「最长公共子序列问题」展开，总结三道子序列问题，解这道题仔细讲讲这种子序列问题的套路，你就能感受到这种思维方式了。

最长公共子序列

给你输入两个字符串 s1 和 s2，请你找出他们俩的最长公共子序列，返回这个子序列的长度。

定义 dp[i][j] 表示 s1[0:i] 和 s2[0:j] 的最长公共子序列长度，代码如下：

字符串的删除操作

给定两个单词 s1 和 s2 ，返回使得 s1 和 s2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。

题目让我们计算将两个字符串变得相同的最少删除次数，那我们可以思考一下，最后这两个字符串会被删成什么样子？

删除的结果不就是它俩的最长公共子序列嘛！

最小 ASCII 删除和

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

这道题不能直接复用计算最长公共子序列的函数，但是可以依照之前的思路，稍微修改 base case 和状态转移部分即可直接写出解法代码：

子序列问题解题模板

两种思路

第一种思路模板是一个一维的 dp 数组：

如我们写过的 最长递增子序列 和 最大子数组和 都是这个思路。

在这个思路中 dp 数组的定义是：

在子数组 arr[0..i] 中，以 arr[i] 结尾的子序列的长度是 dp[i]

为啥最长递增子序列需要这种思路呢？前文说得很清楚了，因为这样符合归纳法，可以找到状态转移的关系，这里就不具体展开了。

第二种思路模板是一个二维的 dp 数组：

这种思路运用相对更多一些，尤其是涉及两个字符串/数组的子序列时，比如前文讲的 最长公共子序列 和 编辑距离；这种思路也可以用于只涉及一个字符串/数组的情景，比如本文讲的回文子序列问题。

2.1 涉及两个字符串/数组的场景，dp 数组的定义如下：

在子数组 arr1[0..i] 和子数组 arr2[0..j] 中，我们要求的子序列长度为 dp[i][j]。

2.2 只涉及一个字符串/数组的场景，dp 数组的定义如下：

在子数组 array[i..j] 中，我们要求的子序列的长度为 dp[i][j]。

最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

我们对 dp 数组的定义是：在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]。一定要记住这个定义才能理解算法。

先明确一下 base case，如果只有一个字符，显然最长回文子序列长度是 1，也就是 dp[i][j] = 1 (i == j)。

因为 i 肯定小于等于 j，所以对于那些 i > j 的位置，根本不存在什么子序列，应该初始化为 0。

状态转移也很显然，如果 s[i]==s[j]，则 +=2，否则看 dp[i+1][j] 和 dp[i][j-1] 谁更大。

为了保证每次计算 dp[i][j]，左下右方向的位置已经被计算出来，只能斜着遍历或者反着遍历：

这里我们选择反着遍历，代码如下：

让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。

和上一题几乎一样，秒了。

当然，也可以直接复用上一题的函数，因为先算出字符串 s 中的最长回文子序列，那些不在最长回文子序列中的字符，就是需要插入的字符。