1143. 最长公共子序列

发表于 2025-12-18 分类于力扣阅读次数： Waline：本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

思路

1. 问题定义

给定两个字符串 \[ \text{text}_1,\ \text{text}_2 \] 求它们的最长公共子序列（Longest Common Subsequence, LCS）的长度。

子序列不要求连续，但要求保持原有相对顺序。

2. 状态定义

设 \[ f[i][j] \] 表示 text1 的前 \(i\) 个字符 与 text2 的前 \(j\) 个字符 的最长公共子序列长度。

该定义具有以下性质：

问题规模可被自然拆分为更小的前缀子问题；
最终答案为 \[ f[n_1][n_2] \] 其中 \(n_1 = |\text{text}_1|\)，\(n_2 = |\text{text}_2|\)。

3. 初始条件（边界）

当任意一个字符串长度为 0 时，LCS 长度为 0： \[ \begin{aligned} f[0][j] &= 0 \quad (0 \le j \le n_2) \\ f[i][0] &= 0 \quad (0 \le i \le n_1) \end{aligned} \] 这对应代码中的整体 memset(f, 0, ...) 初始化。

4. 状态转移方程

考虑 text1[i-1] 与 text2[j-1]。

4.1 字符相等的情况

若 \[ \text{text}_1[i-1] = \text{text}_2[j-1] \] 则这两个字符一定可以作为 LCS 的一个新末尾字符： \[ f[i][j] = f[i-1][j-1] + 1 \] 这是 LCS 中唯一“强制使用对角状态”的情形。

4.2 字符不相等的情况（核心讨论）

若 \[ \text{text}_1[i-1] \ne \text{text}_2[j-1] \] 此时无法同时使用这两个末尾字符，LCS 必然来自以下两种选择之一：

丢弃 text1 的第 \(i\) 个字符 → 转化为子问题 \(f[i-1][j]\)
丢弃 text2 的第 \(j\) 个字符 → 转化为子问题 \(f[i][j-1]\)

因此有标准转移式： \[ f[i][j] = \max \bigl( f[i-1][j],\ f[i][j-1] \bigr) \]

5. 为什么可以去掉 \(f[i-1][j-1]\)

这是本题最容易产生疑惑、但也是理解 LCS DP 的关键点。

5.1 一个重要的单调性事实

对于任意 \(i, j\)，都有： \[ \begin{aligned} f[i-1][j-1] &\le f[i-1][j] \\ f[i-1][j-1] &\le f[i][j-1] \end{aligned} \] 原因：

从 (i-1, j-1) 扩展到 (i-1, j)，只是给 text2 多了一个字符；
从 (i-1, j-1) 扩展到 (i, j-1)，只是给 text1 多了一个字符；
LCS 长度不会因为“可选字符变多”而变小。

5.2 数学上的支配关系（Dominance）

由于上述不等式恒成立： \[ \max \bigl( f[i-1][j],\ f[i][j-1] \bigr) \;\;\ge\;\; f[i-1][j-1] \] 因此在字符不相等时： \[ \max \bigl( f[i-1][j-1],\ f[i-1][j],\ f[i][j-1] \bigr) = \max \bigl( f[i-1][j],\ f[i][j-1] \bigr) \] 也就是说：

f[i-1][j-1] 在该分支中被完全“支配”，永远不可能成为最优来源。

5.3 从“决策语义”角度理解

当末尾字符不相等时：

同时丢弃两个字符（f[i-1][j-1]）等价于“先丢一个，再丢另一个”
但 DP 已经在 f[i-1][j] 和 f[i][j-1] 中完整覆盖了这两种可能

因此显式写出 f[i-1][j-1] 不会带来任何新的最优解路径。

6. 最终答案

完整填表后，最终答案为： \[ \boxed{f[n_1][n_2]} \] 时间复杂度： \[ O(n_1 \cdot n_2) \] 空间复杂度：

普通二维 DP：\(O(n_1 \cdot n_2)\)
滚动数组优化后：\(O(n_2)\)

7. 代码实现与注释

7.1 含冗余状态的二维 DP（理论正确，但非最简）

class Solution {
public:
    static const int maxn = 1e3 + 5;
    int longestCommonSubsequence(string text1, string text2) {
        int f[maxn][maxn];
        int n1 = text1.size(), n2 = text2.size();
        memset(f, 0, sizeof(f)); // 边界：任一字符串为空时 LCS 为 0

        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (text1[i - 1] == text2[j - 1])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else
                    // f[i-1][j-1] 实际被 f[i-1][j] 与 f[i][j-1] 支配
                    f[i][j] = max(f[i - 1][j - 1],
                                  max(f[i - 1][j], f[i][j - 1]));
            }
        }
        return f[n1][n2];
    }
};

7.2 标准且最简的二维 DP（推荐）

class Solution {
public:
    static const int maxn = 1e3 + 5;
    int longestCommonSubsequence(string text1, string text2) {
        int f[maxn][maxn];
        int n1 = text1.size(), n2 = text2.size();
        memset(f, 0, sizeof(f));

        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (text1[i - 1] == text2[j - 1])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else
                    // 去掉 f[i-1][j-1]，不影响正确性
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
        return f[n1][n2];
    }
};

7.3 滚动数组优化版（空间压缩）

class Solution {
public:
    static const int maxn = 1e3 + 5;
    int longestCommonSubsequence(string text1, string text2) {
        int f[2][maxn];
        int n1 = text1.size(), n2 = text2.size();
        memset(f, 0, sizeof(f));

        for (int i = 1; i <= n1; ++i) {
            f[i & 1][0] = 0; // 每一行的左边界
            for (int j = 1; j <= n2; ++j) {
                if (text1[i - 1] == text2[j - 1])
                    f[i & 1][j] = f[(i - 1) & 1][j - 1] + 1;
                else
                    f[i & 1][j] = max(f[(i - 1) & 1][j],
                                      f[i & 1][j - 1]);
            }
        }
        return f[n1 & 1][n2];
    }
};

8. 小结

LCS 的核心在于前缀最优子结构；
当字符不相等时，f[i-1][j-1] 被 f[i-1][j] 与 f[i][j-1] 严格支配；
去掉该状态既不影响正确性，也使状态转移更清晰、更易推广到滚动数组优化；
这是 LCS 与编辑距离等 DP 题型在“转移语义”上的一个重要分界点。