最长公共子序列

更新: 7/3/2026 字数: 0 字 时长: 0 分钟

LeetCode 第 1143 题 · 中等 · 二维动态规划入门必刷题（LCS）

题目描述

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

一个字符串的子序列是指：删除某些字符（也可以不删）后，不改变剩余字符相对顺序得到的新字符串。两个字符串的公共子序列是这两个字符串共有的子序列。

子序列 ≠ 子串

• 子串必须连续："ace" 不是 "abcde" 的子串；
• 子序列只需保持相对顺序、可跳跃："ace" 是 "abcde" 的子序列。

本题的公共子序列不要求连续，这一点与「最长公共子串」不同。

示例：

text1	text2	输出	说明
"abcde"	"ace"	3	最长公共子序列是 "ace"
"abc"	"abc"	3	完全相同
"abc"	"def"	0	没有公共字符
"ABCBDAB"	"BDCAB"	4	如 "BCAB" / "BDAB"

思路拆解：从暴力到最优

第一步：暴力递归（先解出来）

从两个字符串的末尾开始比较，考虑最后一对字符 text1[i-1] 与 text2[j-1]：

• 若相等：这个字符一定可以放进公共子序列，问题缩小为"前面部分的 LCS" + 1；
• 若不等：最后一个字符至多只能属于其中一个串，于是分两种情况——要么丢弃 text1 的末字符，要么丢弃 text2 的末字符，取两者较大值。

写成递归函数 lcs(i, j) 表示 text1[0..i-1] 与 text2[0..j-1] 的 LCS 长度。这样能得到正确答案，但同一个 (i, j) 会被反复计算，时间复杂度高达 。

点击展开暴力递归解法（仅供理解，不推荐）

function lcs_bruteForce(text1, text2) {
  const helper = (i, j) => {
    if (i === 0 || j === 0) return 0;          // 任一串为空
    if (text1[i - 1] === text2[j - 1]) {
      return helper(i - 1, j - 1) + 1;         // 末字符相等
    }
    // 末字符不等：丢弃 text1 或 text2 的末字符
    return Math.max(helper(i - 1, j), helper(i, j - 1));
  };
  return helper(text1.length, text2.length);
}

第二步：二维动态规划（最优）

暴力递归的浪费在于大量重叠子问题。既然 lcs(i, j) 只依赖三个更小的子问题，我们干脆用一张二维表把它们全部存下来，自底向上填表。

定义状态：

dp[i][j] = text1 的前 i 个字符 与 text2 的前 j 个字符 的最长公共子序列长度。

转移方程（本题核心）：

边界：dp[0][j] = dp[i][0] = 0（任一字符串为空时 LCS 为 0）。

核心思路

把二维表多开一行一列当作"空串"边界，避免下标越界判断。填表时：字符相等就取左上角 +1（↖），不相等就取上方和左方的较大值（↑ 或 ←）。最终右下角 dp[m][n] 就是答案。整张表每格 计算，共 格，时间 。

交互式动画演示

下面用样例 text1 = "ABCBDAB"、text2 = "BDCAB" 完整演示二维 DP 的逐格填表过程。点击 下一步 / 自动播放，观察每一格如何根据"字符是否匹配"选择左上角 +1（绿色）还是上/左取最大（橙色来源）：

二维 DP 表 · 最长公共子序列演示

text1 = "ABCBDAB"，text2 = "BDCAB"

	Ø	B	D	C	A	B
Ø	0	0	0	0	0	0
A	0	0	0	0	0	0
B	0	0	0	0	0	0
C	0	0	0	0	0	0
B	0	0	0	0	0	0
D	0	0	0	0	0	0
A	0	0	0	0	0	0
B	0	0	0	0	0	0

当前格参考来源字符匹配(左上+1)已填

当前格—

LCS 长度0

初始化：dp 多开一行一列作为「空串」边界，全部填 0。dp[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。

步骤 0 / 36

观察重点

• Ø 行/列是空串边界，全为 0；蓝色格子是当前正在计算的格；
• 绿色表示当前字符匹配，取左上角 ↖ 的值 +1；
• 橙色表示不匹配时被参考的来源格（上方或左方的较大值）；
• 表格按行从左到右、从上到下填充，右下角绿色闪烁格即最终答案 4。

完整代码（JavaScript）

/**
 * 最长公共子序列 —— 二维动态规划，时间 O(mn)，空间 O(mn)
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.length;
  // 多开一行一列作为空串边界，默认全 0
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        // 字符相等：取左上角 +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]; // 右下角即答案
}

// 测试
console.log(longestCommonSubsequence('abcde', 'ace'));       // 3
console.log(longestCommonSubsequence('abc', 'abc'));         // 3
console.log(longestCommonSubsequence('abc', 'def'));         // 0
console.log(longestCommonSubsequence('ABCBDAB', 'BDCAB'));   // 4

点击展开：滚动数组优化到 O(n) 空间

由于 dp[i][j] 只依赖上一行 dp[i-1][*] 和当前行左边的值，可以用一维数组滚动，把空间从 降到 。关键是用一个临时变量 prev 保存"左上角"的旧值。

function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    let prev = 0; // 相当于 dp[i-1][j-1]
    for (let j = 1; j <= n; j++) {
      const tmp = dp[j];              // 保存旧的 dp[i-1][j]
      if (text1[i - 1] === text2[j - 1]) {
        dp[j] = prev + 1;
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]);
      }
      prev = tmp;                     // 更新左上角
    }
  }
  return dp[n];
}

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力递归			大量重叠子问题，仅用于理解
记忆化递归			自顶向下缓存 (i,j)
二维 DP（推荐）			自底向上填表，最直观
滚动数组 DP			只保留一行，空间最优

其中 、 分别为两个字符串的长度：

边界与易错点

易错点清单

1. 空串边界：任一字符串为空时 LCS 为 0。多开一行一列并初始化为 0，可以省去循环内的越界判断。
2. 下标错位：dp 的下标从 1 开始对应字符，字符串取字符要用 text1[i-1]、text2[j-1]，别写成 text1[i]，这是最高频的 bug。
3. 公共子序列 ≠ 公共子串：本题不要求连续，转移里"不匹配取上/左最大值"正是允许跳过字符。若求的是最长公共子串（连续），转移要改成：不匹配时 dp[i][j] = 0，答案取全表最大值而非右下角。
4. 答案位置：二维 DP 的答案是 dp[m][n]（右下角），这一点与最长公共子串不同，别取 max。
5. 严格性：LCS 不涉及"严格"，字符相等即可累加；重复字符不会造成本题额外坑点。
6. 滚动数组的 prev：一维优化时必须在覆盖 dp[j] 前先保存旧值作为"左上角"，顺序写错会用到本轮已更新的值导致结果偏大。

一句话记忆

"相等取左上加一，不等取上左最大"——一张二维表从左上填到右下，右下角就是最长公共子序列的长度。