最长公共子序列

动态规划 · 填表 + 回溯恢复解

两个串的最长公共子序列

给两个串 X = ABCD 和 Y = ACDF，找它们最长的公共子序列（LCS）。子序列是从原串里按顺序挑出若干字符（不要求连续，区别于子串）。这里的答案是 ACD（长度 3）。LCS 是 diff、git 比对、DNA 序列比对的核心，也是动态规划的又一经典。

二维 DP：逐格填表

设 dp[i][j] 为 X 前 i 个字符与 Y 前 j 个字符的 LCS 长度。空串没有公共子序列，所以第 0 行、第 0 列都是 0。填每一格时看 X[i-1] 和 Y[j-1]：

相同——这个公共字符能接在「各退一格」的 LCS 后面，所以取左上 + 1（dp[i-1][j-1] + 1）；不同——当前这对字符至少有一个用不上，丢掉 X 或 Y 的当前字符取较优的，即取上、左两格的较大值（max(dp[i-1][j], dp[i][j-1])）。填到右下角就是 LCS 的长度。

回溯：从表里恢复出 LCS

但表格只给出长度，LCS字符串本身要回溯出来：从右下角出发倒着走——当前格字符相同，说明它是 LCS 的一员，记下这个字符、往左上对角走；不同，就往上、左中 dp 较大的那格走（当初的值就是从那来的）。一路收集到的字符倒序拼起来就是 LCS。

下面是 X=ABCD、Y=ACDF 的 DP 表。点「下一步」逐步看：先逐格填表（相同取左上 +1、不同取上/左较大，源格黄色、新填绿色）；填满后从右下角回溯，路径格绿环连成一条，匹配处收字符，最终恢复出 ACD。右侧代码随每一步同步高亮。

	A	C	D	F
∅	0	0	0	0
A
B
C
D

边界：空串与任何串的 LCS 长度为 0（第 0 行 / 第 0 列全 0）

1function lcs(x: string, y: string): string {
const m = x.length, n = y.length;
const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    if (x[i - 1] === y[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]);       // 不同：上/左较大
  }
}
let i = m, j = n, s = "";
while (i > 0 && j > 0) {                        // 回溯恢复 LCS
  if (x[i - 1] === y[j - 1]) { s = x[i - 1] + s; i--; j--; }    // 收字符走对角
  else if (dp[i - 1][j] >= dp[i][j - 1]) i--;   // 往大的上/左走
  else j--;
}
return s;
17}

串 XABCD

串 YACDF

1 / 24

填表求值，回溯求解

很多 DP 都是两步：填表求出最优值，再回溯沿「当初的选择」倒推出最优解。
编辑距离同样可回溯出具体的增删改操作序列；0-1 背包可回溯出到底选了哪些物品。本页把「回溯恢复解」讲到最直观。

LCS 与编辑距离是一对近亲：同为两串上的二维 DP，只是递推规则不同（LCS 相同取左上 +1，编辑距离相同取左上、不同取三邻最小 +1）。填表是同一套范式，回溯恢复解则让「表」变回「答案」。

算法可视化

最长公共子序列

两个串的最长公共子序列

二维 DP：逐格填表

回溯：从表里恢复出 LCS

填表求值，回溯求解