学习首页/动态规划/最长公共子序列交互演示 · JavaScript

代码与动画 LONGEST COMMON SUBSEQUENCE

最长公共子序列.

比较两个字符串的前缀，在二维表中计算并回溯公共子序列。

时间 O(mn)空间 O(mn)子序列允许不连续

原理与执行逻辑

dp[i][j] 记录两个字符串前 i、前 j 个字符的最长公共子序列长度。末尾字符相同就接在较短前缀的解后，不同时舍弃其中一方末尾再比较。

执行步骤

  1. 建立带空串行、列的二维表，边界为 0。
  2. 字符相同时取左上格加一。
  3. 字符不同时取上格与左格的较大值。
  4. 从右下角回溯，匹配字符就记录并走左上，其他情况沿较大值方向移动。

关键理解

子序列允许跳过字符，但必须维持原来的相对顺序。表格计算长度，回溯还原一个解；存在多个解时 Demo 优先向上走。

简短示例

ABCDE 与 ACE 的最长公共子序列为 ACE，长度 3；B、D 可以跳过，A、C、E 的顺序保持不变。

代码与执行动画

STEP 0 / 36
最长公共子序列
function lcs(a, b) {  const dp = Array.from({length: a.length + 1}, () => Array(b.length + 1).fill(0));  for (let i = 1; i <= a.length; i++) {    for (let j = 1; j <= b.length; j++) {      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);    }  }  let i = a.length, j = b.length; const sequence = [];  while (i > 0 && j > 0) {    if (a[i - 1] === b[j - 1]) { sequence.push(a[i - 1]); i--; j--; }    else if (dp[i - 1][j] >= dp[i][j - 1]) i--;    else j--;  }  return sequence.reverse().join('');}
15 行 · 0 个片段标记
∅ACE∅0000A0000B0000C0000D0000E0000
当前数据正在操作已访问 / 命中标记 / 指针
0

初始化公共子序列表

行对应 A 的前缀，列对应 B 的前缀；空串与任何前缀的公共长度为 0。

配置演示数据

应用后重新生成执行过程，可单步观察结果。

实现说明

最长公共子序列的操作规则

匹配时取左上格加一，否则取上格与左格的较大值。回溯得到一个最长公共子序列；存在多个解时优先向上移动。

对应题目与扩展练习

观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。