经典面试题：最长公共子序列

怼烎@ 2024-04-17 17:38 69阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | labuladong

来源 | labuladong

最长公共子序列（Longest Common Subsequence，简称 LCS）是一道非常经典的面试题目，因为它的解法是典型的二维动态规划，大部分比较困难的字符串问题都和这个问题一个套路，比如说编辑距离。而且，这个算法稍加改造就可以用于解决其他问题，所以说 LCS 算法是值得掌握的。

题目就是让我们求两个字符串的 LCS 长度：

输入: str1 = "abcde", str2 = "ace" 
    输出: 3  
    解释: 最长公共子序列是 "ace"，它的长度是 3

肯定有读者会问，为啥这个问题就是动态规划来解决呢？因为子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。所以可以说只要涉及子序列问题，十有八九都需要动态规划来解决，往这方面考虑就对了。

下面就来手把手分析一下，这道题目如何用动态规划技巧解决。

### 一、动态规划思路 ###

**第一步，一定要明确`dp`数组的含义**。对于两个字符串的动态规划问题，套路是通用的。

比如说对于字符串`s1`和`s2`，一般来说都要构造一个这样的 DP table：

![640?wx\_fmt=png][640_wx_fmt_png]

为了方便理解此表，我们暂时认为索引是从 1 开始的，待会的代码中只要稍作调整即可。其中，`dp[i][j]`的含义是：对于`s1[1..i]`和`s2[1..j]`，它们的 LCS 长度是`dp[i][j]`。

比如上图的例子，d\[2\]\[4\] 的含义就是：对于`"ac"`和`"babc"`，它们的 LCS 长度是 2。我们最终想得到的答案应该是`dp[3][6]`。

**第二步，定义 base case。**

我们专门让索引为 0 的行和列表示空串，`dp[0][..]`和`dp[..][0]`都应该初始化为 0，这就是 base case。

比如说，按照刚才 dp 数组的定义，`dp[0][3]=0`的含义是：对于字符串`""`和`"bab"`，其 LCS 的长度为 0。因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0。

**第三步，找状态转移方程。**

这是动态规划最难的一步，不过好在这种字符串问题的套路都差不多，权且借这道题来聊聊处理这类问题的思路。

状态转移说简单些就是做选择，比如说这个问题，是求`s1`和`s2`的最长公共子序列，不妨称这个子序列为`lcs`。那么对于`s1`和`s2`中的每个字符，有什么选择？很简单，两种选择，要么在`lcs`中，要么不在。

![640?wx\_fmt=png][640_wx_fmt_png 1]

这个「在」和「不在」就是选择，关键是，应该如何选择呢？这个需要动点脑筋：如果某个字符应该在`lcs`中，那么这个字符肯定同时存在于`s1`和`s2`中，因为`lcs`是最长**公共**子序列嘛。所以本题的思路是这样：

用两个指针`i`和`j`从后往前遍历`s1`和`s2`，如果`s1[i]==s2[j]`，那么这个字符**一定在`lcs`中**；否则的话，`s1[i]`和`s2[j]`这两个字符**至少有一个不在`lcs`中**，需要丢弃一个。先看一下递归解法，比较容易理解：

![640?wx\_fmt=png][640_wx_fmt_png 2]

对于第一种情况，找到一个`lcs`中的字符，同时将`i, j`向前移动一位，并给`lcs`的长度加一；对于后者，则尝试两种情况，取更大的结果。

其实这段代码就是暴力解法，我们可以通过备忘录或者 DP table 来优化时间复杂度，比如通过前文描述的 DP table 来解决：

![640?wx\_fmt=png][640_wx_fmt_png 3]

### 二、疑难解答 ###

对于`s1[i]`和`s2[j]`不相等的情况，**至少有一个**字符不在`lcs`中，会不会两个字符都不在呢？比如下面这种情况：

![640?wx\_fmt=png][640_wx_fmt_png 4]

所以代码是不是应该考虑这种情况，改成这样：

if str1[i - 1] == str2[j - 1]:
        # ...
    else:
        dp[i][j] = max(dp[i-1][j], 
                       dp[i][j-1],
                       dp[i-1][j-1])

我一开始也有这种怀疑，其实可以这样改，也能得到正确答案，但是多此一举，因为`dp[i-1][j-1]`永远是三者中最小的，max 根本不可能取到它。

原因在于我们对 dp 数组的定义：对于`s1[1..i]`和`s2[1..j]`，它们的 LCS 长度是`dp[i][j]`。

![640?wx\_fmt=png][640_wx_fmt_png 5]

这样一看，显然`dp[i-1][j-1]`对应的`lcs`长度不可能比前两种情况大，所以没有必要参与比较。

### 三、总结 ###

对于两个字符串的动态规划问题，一般来说都是像本文一样定义 DP table，因为这样定义有一个好处，就是容易写出状态转移方程，`dp[i][j]`的状态可以通过之前的状态推导出来：

![640?wx\_fmt=png][640_wx_fmt_png 6]

找状态转移方程的方法是，思考每个状态有哪些「选择」，只要我们能用正确的逻辑做出正确的选择，算法就能够正确运行。

![640?wx\_fmt=png][640_wx_fmt_png 7]

**热门推荐** ![640?wx\_fmt=gif][640_wx_fmt_gif]

1.【程序员】[全球最厉害的 14 位程序员][14]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了][Link 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/9e139de7bb8a403dab4aa4f72609270d.png
[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/a562e273d76a497c8b5c812da8e45d20.png
[640_wx_fmt_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/4eaa781b07f04011a25fa216da1930b1.png
[640_wx_fmt_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f354f89caa8a49dfbbffe43e259aeed7.png
[640_wx_fmt_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/2d22930807444f9a9769a91fd96f22a3.png
[640_wx_fmt_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/18087c08c50b4f719214c3af4163d66b.png
[640_wx_fmt_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/51cf6196fe974ebb88a792f22d978a4c.png
[640_wx_fmt_png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/dfdc882ad4d048848c12770da770e195.png
[640_wx_fmt_png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/365dc0c771f840359d88f2d08f2a7b28.png
[640_wx_fmt_gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/83727871a15f4a79b256e3fbd9e3c2b2.gif
[14]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486099&idx=1&sn=6ea84944fe6a3d6dd1af2b00f3e53002&chksm=fa0e6512cd79ec04c8e8c63e74d78cc23629b88290a8e0642e5e44601f99fc39a3ea530867bc&scene=21#wechat_redirect
[GitHub]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486254&idx=1&sn=654c208601879fe1b76c682a069a4e6a&chksm=fa0e64afcd79edb960a9863c7af7e6de5893da2326e6eca2bcd9d68061966d200ba0e189ab91&scene=21#wechat_redirect
[KMP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485939&idx=1&sn=b25f39b5644da92c4047bbbd9936f73c&chksm=fa0e6672cd79ef64dda0a21e23c2817edf4a64cbb75b9bed328d6519c6cd4fef36d03a4cb309&scene=21#wechat_redirect
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[640_wx_fmt_jpeg 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/c5bad043ca1b463498baa8ff1430519f.png