经典 dp 模型：最长公共子序列问题

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的 1143. 最长公共子序列 ，难度为中等。

Tag : 「最长公共子序列」、「LCS」、「序列 DP」

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

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

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 

输出：3  

解释：最长公共子序列是 "ace" ，它的长度为 3 。
复制代码

示例 2：

输入：text1 = "abc", text2 = "abc"

输出：3

解释：最长公共子序列是 "abc" ，它的长度为 3 。
复制代码

示例 3：

输入：text1 = "abc", text2 = "def"

输出：0

解释：两个字符串没有公共子序列，返回 0 。
复制代码

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

动态规划【空格技巧】

这是一道「最长公共子序列（LCS）」的裸题。

对于这类题的都使用如下「状态定义」即可：

$f[i][j]$ 代表考虑 $s1$ 的前 $i$ 个字符、考虑 $s2$ 的前 $j$ 的字符，形成的最长公共子序列长度。

当有了「状态定义」之后，基本上「转移方程」就是呼之欲出：

s1[i]==s2[j] : $f[i][j]=f[i-1][j-1]+1$ 。代表必然使用 $s1[i]$ 与 $s2[j]$ 时 LCS 的长度。
s1[i]!=s2[j] : $f[i][j]=max(f[i-1][j], f[i][j-1])$ 。代表必然不使用 $s1[i]$ （但可能使用 $s2[j]$ ）时 和 必然不使用 $s2[j]$ （但可能使用 $s1[i]$ ）时 LCS 的长度。

一些编码细节：

通常我会习惯性往字符串头部追加一个空格，以减少边界判断（使下标从 1 开始，并很容易构造出可滚动的「有效值」）。

代码：

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        s1 = " " + s1; s2 = " " + s2;
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1]; 

        // 因为有了追加的空格，我们有了显然的初始化值（以下两种初始化方式均可）
        // for (int i = 0; i <= n; i++) Arrays.fill(f[i], 1);
        for (int i = 0; i <= n; i++) f[i][0] = 1;
        for (int j = 0; j <= m; j++) f[0][j] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i] == cs2[j]) {
                    f[i][j] = f[i -1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }

        // 减去最开始追加的空格
        return f[n][m] - 1;
    }
}
复制代码

时间复杂度： $O(n * m)$
空间复杂度： $O(n * m)$

动态规划【利用偏移】

上述「追加空格」的做法是我比较习惯的做法 ?

事实上，我们也可以通过修改「状态定义」来实现递推：

$f[i][j]$ 代表考虑 $s1$ 的前 $i – 1$ 个字符、考虑 $s2$ 的前 $j – 1$ 的字符，形成的最长公共子序列长度。

那么最终的 $f[n][m]$ 就是我们的答案， $f[0][0]$ 当做无效值，不处理即可。

s1[i-1]==s2[j-1] : $f[i][j]=f[i-1][j-1]+1$ 。代表使用 $s1[i-1]$ 与 $s2[j-1]$ 形成最长公共子序列的长度。
s1[i-1]!=s2[j-1] : $f[i][j]=max(f[i-1][j], f[i][j-1])$ 。代表不使用 $s1[i-1]$ 形成最长公共子序列的长度、不使用 $s2[j-1]$ 形成最长公共子序列的长度。这两种情况中的最大值。

代码：

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1]; 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[n][m];
    }
}
复制代码