最长公共子序列（LCS）如何用动态规划求解？（LeetCode 1143）

简化版

最长公共子序列（LCS）：求两个字符串里都出现、且顺序一致（可不连续）的最长子序列长度。用二维 DP：dp[i][j] = 「a 的前 i 个字符和 b 的前 j 个字符的 LCS 长度」。转移看当前两个字符是否相等——相等则 dp[i][j] = dp[i-1][j-1] + 1（这个公共字符接上去）；不等则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])（放弃其中一个字符，取较优）。答案 dp[m][n]。

详细版

int longestCommonSubsequence(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];         // 多开一行一列表示「空前缀」
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.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[i][j] = a[0..i-1] 与 b[0..j-1] 的 LCS 长度（dp 下标比字符下标大 1）。
转移方程：
- a[i-1] == b[j-1]：dp[i][j] = dp[i-1][j-1] + 1；
- 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
初始化：dp[0][*] = dp[*][0] = 0（任一串为空，LCS 为 0）。
复杂度：O(m·n) 时间、O(m·n) 空间（可滚动数组压到 O(n)）。

完整版教学

一、问题：公共子序列（可不连续）

LCS：a = "abcde"、b = "ace"，最长公共子序列是 "ace"，长度 3。要点同样是子序列可以不连续——a、c、e 在 abcde 里并不相邻，但顺序一致，就算公共子序列。它是双序列 DP 的代表模型，编辑距离、最短公共超序列、不同的子序列等都从它衍生。

别和最长公共子串（substring） 混——子串要求连续，那是另一道题（转移方程不同，见第五节）。

二、状态定义（前缀思想）

定义状态：dp[i][j] = 「字符串 a 的前 i 个字符（a[0..i-1]）和 b 的前 j 个字符（b[0..j-1]）的最长公共子序列长度」。

这里用了 DP 处理双序列的经典技巧——用「前缀长度」当状态维度，并且 dp 数组多开一行一列（大小 (m+1)×(n+1)），下标 0 表示「空前缀」。所以 dp[i][j] 对应的实际字符是 a[i-1] 和 b[j-1]（下标错开 1），这样能优雅地处理边界，不必特判空串。

三、转移方程：字符相等 vs 不等

考虑 a 的第 i 个字符 a[i-1] 和 b 的第 j 个字符 b[j-1]：

两字符相等（a[i-1] == b[j-1]）：这个字符可以作为公共子序列的新末尾，接在「a 前 i-1、b 前 j-1 的 LCS」后面，长度 +1：
```
dp[i][j] = dp[i-1][j-1] + 1
```

两字符不等：这个位置凑不出公共字符，那就放弃 a[i-1] 或放弃 b[j-1]，看哪种能得到更长的 LCS：

dp[i][j] = max( dp[i-1][j],   // 不要 a 的第 i 个字符
                dp[i][j-1] )  // 不要 b 的第 j 个字符

理解「不等时取 max」的关键：dp[i-1][j] 意味着「a 少用一个字符」，dp[i][j-1] 意味着「b 少用一个字符」，两条路都试，保留更优的。

四、初始化与遍历

初始化：dp[0][j] = 0、dp[i][0] = 0——只要有一个串是空前缀，公共子序列长度必然是 0。多开的这一行一列全为 0，正好当递推起点。
遍历顺序：dp[i][j] 依赖左上 dp[i-1][j-1]、上 dp[i-1][j]、左 dp[i][j-1]，所以按 i、j 都从小到大双层循环，保证依赖项先算好。
答案：dp[m][n]（两个完整串的 LCS）。

五、和最长公共子串（连续）的区别

一字之差，转移方程却不同，是高频对比：

	最长公共子序列（LCS）	最长公共子串（substring）
是否要连续	不要求连续	要求连续
字符相等	`dp[i][j]=dp[i-1][j-1]+1`	`dp[i][j]=dp[i-1][j-1]+1`（同）
字符不等	`max(dp[i-1][j], dp[i][j-1])`	`dp[i][j]=0`（断了就归零）
答案位置	`dp[m][n]`	所有 `dp[i][j]` 的最大值

公共子串因为要连续，一旦字符不匹配就「断开」dp[i][j]=0，且答案是全表最大值而非右下角。搞清「不等时是取 max 还是清零」，就分清了这对孪生题。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：dp[i][j] 是两个字符串前 i、前 j 个字符的 LCS 长度。

转移过程是：末字符相等时 dp[i-1][j-1]+1；不等时取丢弃任一末字符的 max(dp[i-1][j],dp[i][j-1])。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：abcde 与 ace 的状态依次匹配 a、c、e，最终 LCS 长度 3。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：子序列不要求连续；相等分支可直接取对角+1；恢复具体 LCS 在不等且两前驱相同时存在多条答案。

核对项	本题答案
复杂度	O(mn) 时间与空间，长度可滚动到 O(min(m,n))
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：LCS 等同最长公共子串。 子序列允许跳过字符，子串要求连续。
误区：字符不等时应看 dp[i-1][j-1]。 至少要尝试丢弃其中一个末字符。
误区：滚动数组方向随意。 当前行左值与上一行同列/左上依赖必须避免覆盖。
追问：相等时为何加 1？ 可把共同末字符接到两个更短前缀的 LCS 后。
追问：怎样恢复一个 LCS？ 从右下回溯：相等走对角，不等走较大前驱。
追问：如何求最长公共子串？ 不等时状态归零，并维护全局最大值。

九、加强记忆

LCS 求两串公共、顺序一致、可不连续的最长子序列。二维 DP：dp[i][j] = a 前 i 与 b 前 j 的 LCS 长度（数组多开一行列，下标错 1）。转移——字符相等 dp[i][j]=dp[i-1][j-1]+1；不等 dp[i][j]=max(dp[i-1][j], dp[i][j-1])。空串初始化为 0，答案 dp[m][n]。对比最长公共子串（连续）：不等时改为 dp[i][j]=0、答案取全表最大值。

简化版

详细版