LeetCode 例题精讲 | 15 最长公共子序列：二维动态规划的解法

点击关注上方“五分钟学算法”，

设为“置顶或星标”，第一时间送达干货。

转自面向大象编程

本期例题：LeetCode 1143. Longest Common Subsequence 最长公共子序列(Medium)

给定两个字符串 s 和 t，返回这两个字符串的最长公共子序列的长度。若这两个字符串没有公共子序列，则返回 0。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。例如，"ace" 是 "abcde" 的子序列。

在上一篇文章中，我们以打家劫舍(House Robber)问题为例讲解了动态规划问题的一般解题步骤。不过，打家劫舍问题是一维动态规划问题，而还有很多题目属于二维动态规划。今天我们就以一道经典的「最长公共子序列」问题讲解二维动态规划的解法。

最长公共子序列问题经典到什么程度呢？经典到有自己的专用缩写 —— LCS (Longest Common Subsequence)。如果你在别的地方看到 LCS 的缩写，要能够知道这是最长公共子序列的问题。

如果说打家劫舍问题是动态规划的最佳入门题，那么 LCS 问题就是二维动态规划的最佳入门题，问题经典，方法典型。本文会在一步步求解 LCS 问题的过程中，讲解二维动态规划问题的解题要领。

本文假设你已经了解了打家劫舍问题的解法以及动态规划问题的基本解题步骤。对此不是很清楚的同学可以回顾一下上一篇文章：

LeetCode 例题精讲 | 14 打家劫舍问题：动态规划的解题四步骤

一维与二维动态规划

首先我们要清楚一维动态规划与二维动态规划的含义。对于打家劫舍问题，我们定义 为偷前 间房子的最大金额。这里子问题只有一个参数 ，因此是一维动态规划问题，参数只会在一个维度上变化。而如果子问题有两个参数，则为二维动态规划问题，参数会在两个维度上变化。

为什么要区分子问题的维度呢？这是因为子问题的维度会直接影响 DP 数组的维度。二维的 DP 数组不仅空间复杂度变大，DP 数组的计算顺序也更复杂。

一般来说，绝大多数动态规划问题的维度不会超过二维。必须使用三维以上子问题的题目属于难题，不需要掌握。

使用四步骤解题

在上一篇文章中，我们讲解了动态规划题目的的四个基本解题步骤：

• 定义子问题

• 写出子问题的递推关系

• 确定 DP 数组的计算顺序

• 空间优化(可选)

二维动态规划问题同样遵循这四个解题步骤，不过每个步骤可能会更复杂。下面我们使用四步骤方法一步步解决 LCS 问题。

步骤一：定义子问题

要定义子问题，我们还是抓住这样一个子问题的基本性质：子问题是和原问题相似，但规模较小的问题。

对于 LCS 问题，原问题是「s 和 t 的最长公共子序列」。那么子问题可以缩小字符串 s 或者 t 的规模，变成「s 的前 个字符(s[0..i))和 t 的前 个字符(t[0..j))的最长公共子序列」，用 表示。

可以看到，子问题有 、 两个参数，属于二维 DP 问题。

LCS 问题的子问题定义

步骤二：写出子问题的递推关系

这一步是求解动态规划问题最关键的一步。二维的子问题有很多可能的递推关系，有些题目一目了然，有些则可能需要仔细推敲。

一般来说，我们首先思考能不能使用一种最简单的子问题递推关系：看当前子问题和前一个子问题的关系。如果是一维子问题，就是看 和 的关系；如果是二维子问题，则是看 和 、 、 的关系。LCS 问题就是这种简单递推关系的代表。

LCS 问题的子问题 代表「s[0..i) 和 t[0..j) 的最长公共子序列」。我们可以比较 s 和 t 的最后一个字符 s[i-1] 和 t[j-1]。那么，这可能会有两种情况：

第一种情况：如果 s[i-1] == t[j-1] ，我们可以用这个字符作为最长公共子序列中的字符，然后找 s[0..i-1) 和 t[0..j-1) 的最长公共子序列，如下图所示。

子问题的递推关系，情况一

第二种情况：如果 s[i-1] != t[j-1]，我们可以试着删掉 s 或者 t 末尾的一个字符，即比较 s[0..i-1) 与 t[0..j)，或者比较 s[0..i) 与 t[0..j-1)，两种方案中，选择较长的公共子序列，如下图所示。

子问题的递推关系，情况二

这样，我们得到的子问题递推关系为：

我们还要注意写出递推关系的 base case。当 时，s[0..i) 为空，s[0..i) 和 t[0..j) 的最长公共子序列长度为 。因此 。同样地，当 时，t[0..j) 为空， 。

步骤三：确定 DP 数组的计算顺序

对于二维动态规划问题，我们仍然要坚持使用 DP 数组，用自底向上的顺序计算子问题。因为 DP 数组中的每一个元素都对应一个子问题，当子问题变成二维之后，DP 数组也需要是二维数组。在 DP 数组中，dp[i][j] 对应子问题 ，即 s[0..i) 和 t[0..j) 的最长公共子序列，如下图所示。

DP 数组与子问题的对应关系

在上一篇打家劫舍问题的讲解中，我们直接给出了 DP 数组应该从左向右计算的结论。对于一维动态规划问题，我们可以凭直觉确定 DP 数组的计算顺序。但是对于二维动态规划问题，我们需要有一定的方法来思考 DP 数组的计算顺序。

DP 数组计算顺序的基本原则是：当我们计算一个子问题时，它所依赖的其他子问题应该已经计算好了。 根据这个原则，我们思考三点内容。

第一点：DP 数组的有效范围是什么？ 设 s 的长度为 ，t 的长度为 ，则 、 的取值范围分别为： 。那么我们在声明 DP 数组的时候就应该写：

int[][] dp = new int[m+1][n+1];

二维 DP 数组的整个正方形区域都是合法的。

第二点：base case 和原问题在 DP 数组中在什么位置？ 如下图所示，base case 位于 DP 数组的最左侧一列和最上方一行，而原问题则位于 DP 数组的右下角。

DP 数组中，base case 和原问题的位置

第三点：DP 数组的子问题依赖方向是什么？ 观察子问题的递推关系， 依赖于 、 和 。我们画出 dp[i][j] 和 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 的关系，并画出依赖方向的箭头：

DP 数组中子问题的依赖方向

我们发现，子问题的依赖方向是向右、向下的，因此 DP 数组的计算顺序也应该是从左到右、从上到下。也就是说我们应该以这样的顺序遍历 DP 数组：

for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= n; j++) {
        // 计算 dp[i][j] ...
    }
}

而循环里面的内容，照着子问题的递推关系填进去就可以了。这样，我们的题解代码可以很轻松地写出来：

public int longestCommonSubsequence(String s, String t) {
    if (s.isEmpty() || t.isEmpty()) {
        return 0;
    }
    // 子问题：
    // f(i, j) = s[0..i) 和 t[0..j) 的最长公共子序列
 
    // f(0, *) = 0
    // f(*, 0) = 0
    // f(i, j) = f(i-1, j-1) + 1, if s[i-1] == t[j-1]
    //           max{ f(i-1, j), f(i, j-1) }, otherwise
 
    int m = s.length();
    int n = t.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
    }
    return dp[m][n];
}

上面的代码中还写了一大段关于子问题定义、子问题递推关系的公式。在面试的时候，我们最好把这些东西都写出来，一方面让自己写代码有个参考，另一方面可以让面试官理解自己的思路。

步骤四：空间优化(可选)

二维动态规划问题的 DP 数组变成了二维数组，空间复杂度更高了。因此，二维动态规划问题也更值得进行空间优化，降低空间复杂度。

不过，二维动态规划问题的空间优化有很多种方法，需要根据不同的情况灵活使用。空间优化的步骤是可选的，优化不优化都可以。后面我会专门写一篇文章介绍各种空间优化的方法。

对于这道 LCS 题目，我直接给出空间优化后的代码，使用一维数组 + 临时变量，有兴趣的小伙伴可以自己思考为什么可以这么优化。

public int longestCommonSubsequence(String s, String t) {
    if (s.isEmpty() || t.isEmpty()) {
        return 0;
    }
 
    int m = s.length();
    int n = t.length();
    int[] dp = new int[n+1]; // new 出的数组会默认初始化为 0
    for (int i = 1; i <= m; i++) {
        int temp = 0;
        for (int j = 1; j <= n; j++) {
            int dp_j;
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp_j = temp + 1;
            } else {
                dp_j = Math.max(dp[j], dp[j-1]);
            }
            temp = dp[j];
            dp[j] = dp_j;
        }
    }
    return dp[n];
}

不过需要注意的是，空间优化方法只能优化空间复杂度，不能优化时间复杂度。例如 LCS 问题在空间优化前后的复杂度为：

• 优化前：时间复杂度 ，空间复杂度 。

• 优化后：时间复杂度 ，空间复杂度 。

总结

本文用最长公共子序列(LCS)问题展示了二维动态规划问题的基本解题思路。动态规划问题无论一维二维，都离不开四个基本解题步骤，我们在解题的时候需要牢记这四步骤。

相比一维动态规划，二维动态规划最复杂的地方在于子问题的递推关系与计算顺序。LCS 问题作为入门题，DP 数组的计算顺序还很常规，而后面的「区间 DP」和「背包 DP」问题将会使你脑洞大开。

很多二维动态规划问题都可以看到 LCS 问题的影子。例如「编辑距离」问题，虽然推导方式不太一样，但思路和子问题依赖方式都和 LCS 问题很像。再例如「最长回文子序列」问题，好像是把 LCS 问题的子问题依赖方向旋转了一下。这些题型我们后面都会逐步讲到。

---

推荐阅读

•   LeetCode 例题精讲 | 05 双指针×链表问题：快慢指针•   LeetCode 例题精讲 | 01 反转链表：如何轻松重构链表•   LeetCode 例题精讲 | 04 用双指针解 Two Sum：缩减搜索空间•   LeetCode 例题精讲 | 14 打家劫舍问题：动态规划的解题四步骤•   如何成为一个更好的程序员，或者说是学习者？给你七个建议！•   在拼多多上班，是一种什么样的体验？我tm心态崩了呀！•   写给小白，从零开始拥有一个酷炫上线的网站！

---

欢迎关注我的公众号“五分钟学算法”，如果喜欢，麻烦点一下“在看”~