最长公共子序列和编辑距离怎样用动态规划求？

简答

文本对比工具要找出两段文字里没变的部分，搜索框要判断用户输入的 horse 离 ros 有多远。前一个是最长公共子序列：两个字符串里按相同顺序都出现过的字符，最多能有几个，不要求连续。后一个是编辑距离：通过插入、删除、替换一个字符，最少几步能把一个变成另一个。

两题都用二维的动态规划。dp[i][j] 表示第一个字符串的前 i 个字符和第二个字符串的前 j 个字符之间的答案，每次只看两个前缀的最后一个字符。

最长公共子序列：最后一个字符相同，它一定可以放进公共子序列，答案是 dp[i-1][j-1] + 1；不同，就去掉其中一个字符再比，取 dp[i-1][j] 和 dp[i][j-1] 的较大值。编辑距离：最后一个字符相同，不用操作，等于 dp[i-1][j-1]；不同，就在删除、插入、替换三种操作里选步数最少的，再加 1。

两题的初始值不一样，最容易写错。最长公共子序列里，空串和任何字符串的公共子序列长度都是 0；编辑距离里，空串变成长度为 j 的字符串要插入 j 次，所以第一行是 0、1、2……第一列也一样。时间复杂度都是 O(mn)。

两题的写法

下面两个函数结构几乎一样，表格多开一行一列，用来放空串的情况。

function longestCommonSubsequence(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i += 1) {
    for (let j = 1; j <= b.length; j += 1) {
      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]);
    }
  }
  return dp[a.length][b.length];
}

function minDistance(a, b) {
  const dp = Array.from({ length: a.length + 1 }, (_, i) =>
    Array.from({ length: b.length + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)),
  );
  for (let i = 1; i <= a.length; i += 1) {
    for (let j = 1; j <= b.length; j += 1) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        // 删除 a 的末尾、在 a 末尾插入 b[j-1]、把 a 的末尾替换成 b[j-1]
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[a.length][b.length];
}

console.log(longestCommonSubsequence('abcde', 'ace')); // 3
console.log(longestCommonSubsequence('abc', 'def')); // 0
console.log(minDistance('horse', 'ros')); // 3
console.log(minDistance('intention', 'execution')); // 5
console.log(minDistance('', 'abc')); // 3

前四个输入都是 LeetCode 题面里的例子。'abcde' 和 'ace' 的公共子序列是 ace，长度 3；horse 变成 ros 要三步：h 换成 r，删掉 r，删掉 e。

为什么 a[i - 1] 要减 1？因为 dp 多开了一行一列，dp[i] 对应的是前 i 个字符，最后一个字符的下标是 i - 1。多开这一行一列的好处是，空串的情况直接写在第 0 行和第 0 列，循环里不用判断越界。

编辑距离的三种操作怎样对应三个格子

dp[i][j] 是把 a 的前 i 个字符变成 b 的前 j 个字符的最少步数。最后一个字符不同时，最后一步只可能是三种操作之一。

删除：把 a 的第 i 个字符删掉，剩下的问题是把 a 的前 i-1 个变成 b 的前 j 个，就是 dp[i-1][j]。插入：在 a 后面插入 b[j-1]，这样 b 的最后一个字符就对上了，剩下的问题是把 a 的前 i 个变成 b 的前 j-1 个，就是 dp[i][j-1]。替换：把 a 的最后一个字符换成 b 的最后一个字符，两边都对上了，剩下 dp[i-1][j-1]。

所以取三者的最小值加 1。最长公共子序列只有两个方向，是因为它没有“替换”这个选项：末尾不同时，只能放弃其中一个字符。

怎样省空间

dp[i][j] 只用到上一行和当前行，所以可以只保留一行，空间从 O(mn) 降到 O(n)。要注意，从左往右覆盖时，dp[i-1][j-1] 会在算 dp[i][j-1] 时被覆盖掉，所以要先用一个变量把它存下来。面试时先写出二维版本，再说明可以这样压缩，一般就够了。

动态规划的基本思路，比如怎样定义状态、怎样找转移方程，见《动态规划怎么入门？爬楼梯和最长递增子序列怎样做？》。

常见追问

怎样把最长公共子序列本身找出来，而不只是长度？

填完表以后从右下角往回走。两个字符相同，说明这个字符在子序列里，记下来，往左上角走；不同，就往 dp 值较大的那一边走。走到第 0 行或第 0 列为止，把记下的字符反过来，就是一个最长公共子序列。

子序列和子串有什么区别？

子序列只要求顺序不变，中间可以跳过字符，ace 是 abcde 的子序列；子串必须连续，ace 就不是 abcde 的子串。求最长公共子串时，末尾不同的格子要直接设为 0，因为连续的串在这里断了。