最长公共子序列 图解题解

最长公共子序列，为什么可以跳着挑字符

给两个字符串 text1、text2，各删掉若干字符后，找最长的公共部分。子序列是跳着挑的字符：剩下的按原顺序排好就行，不必挨着，这和「必须连续截一段」的子串不同。题面 text1 = "ABCD"、text2 = "ACBAD"，最长公共子序列长 3，比如 "ABD"。

把所有子序列都列出来，为什么算不完

把 text1 每个子序列都拼出来到 text2 里核对，长度 m 的串有 2^m 个子序列（每字符选或不选），串一长指数爆炸枚举不完。既然前缀比对被反复重验，就把「text1 前 i 个、text2 前 j 个字符的最长公共子序列多长」算一次存下来复用。

一张二维表，dp[i][j] 到底存什么

用动态规划（把「text1 前 i、text2 前 j 个字符的答案」存进表、后面直接取不重算）：dp[i][j] 就是 text1 前 i、text2 前 j 个字符的最长公共子序列长度，(i,j) 是（行号，列号）从 0 数起，一格即一个状态（推进到哪一步、手里那个答案）。表比两串各多开一圈，第 0 行、第 0 列填 0（任一串取 0 个字符时公共部分就是 0）；这圈 0 是地基，靠它每格都能直接看左上、上、左三个邻格。

相等接左上、不等取较大，凭什么是对的

表多开了一圈，dp[i][j] 里的当前两字符其实是 text1[i-1]、text2[j-1]。它俩相等时，这个公共字符能接到「两边都还没用它」那段答案后加一，而那正是斜上方 dp[i-1][j-1]，故 dp[i][j] = dp[i-1][j-1] + 1。不等时两字符不能同用，就在正上 dp[i-1][j] 与正左 dp[i][j-1] 里取较大，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。这就是递推（拿邻格推出当前格）。

拿 ABCD 和 ACBAD 逐格把表填出来

text1 = "ABCD" 作行、text2 = "ACBAD" 作列，第 0 行、第 0 列铺 0。第 1 行填 A：和 text2 的两个 A 相等、都接左上 0 得 1，其余取较大也是 1，整行 1 1 1 1 1。

第 2 行 B：第三列相等 dp[2][3] 接左上 dp[1][2]=1 得 2，整行 1 1 2 2 2。第 3 行 C 同理，整行 1 2 2 2 2。第 4 行 D：末列相等 dp[4][5] 接左上 dp[3][4]=2 得 3，整行 1 2 2 2 3。右下角 3 就是答案。

dp 下标错记成 text1[i]，整张表为什么会全错位

表满 m×n 格、每格常数时间，时间 O(m·n)（大 O 记号，描述串变长时计算量怎么涨）；空间也是一张表 O(m·n)，只求长度时每格只依赖上一行和本行左边，留两行滚着填（滚动数组：留最近几行覆盖旧值）压到 O(min(m,n))。最坑的是下标错位：dp[i][j] 对的是 text1[i-1]、text2[j-1]，写成 text1[i]、text2[j] 就整体偏一格、整张表全错。边界都被那圈 0 兜住：两串全同取到全长，空串或毫无公共都取 0。

Python

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0]*(n+1) for _ in range(m+1)]   # 多一圈 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1       # 相等:左上+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 不等:取大
    return dp[m][n]                          # 右下角即答案

Java

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1] + 1;        // 相等:左上+1
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // 取大
        }
    }
    return dp[m][n];
}

C++

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;        // 相等:左上+1
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // 取大
        }
    }
    return dp[m][n];
}