72.编辑距离

1.`dp` 数组含义

定义二维数组 dp：

dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符，最少需要多少次操作。

这里的操作包括三种：

插入一个字符
删除一个字符
替换一个字符

注意 i 和 j 表示的是“前几个字符”，不是字符串下标。

例如：

word1 = "horse"
word2 = "ros"

dp[3][2] 表示把 word1 的前 3 个字符 "hor" 转换成 word2 的前 2 个字符 "ro" 的最少操作数。

题目要求把整个 word1 转换成整个 word2，所以最终答案就是：

dp[word1.length][word2.length]

2. 确定状态转移方程

假设当前正在计算 dp[i][j]，也就是：

word1 的前 i 个字符 -> word2 的前 j 个字符

此时需要比较两个前缀的最后一个字符：

word1[i - 1]
word2[j - 1]

当前字符相同

如果 word1[i - 1] === word2[j - 1]，说明最后一个字符已经一样，不需要额外操作。

此时只需要看前面的字符怎么转换：

dp[i][j] = dp[i - 1][j - 1];

例如 "ho" 转换成 "ro" 时，最后一个字符都是 o，所以问题变成 "h" 转换成 "r"。

当前字符不同

如果 word1[i - 1] !== word2[j - 1]，最后一个字符不同，有三种选择。

第一种，删除 word1[i - 1]：

dp[i - 1][j] + 1

含义是：先把 word1 的前 i - 1 个字符转换成 word2 的前 j 个字符，再删除当前多出来的 word1[i - 1]。

第二种，插入 word2[j - 1]：

dp[i][j - 1] + 1

含义是：先把 word1 的前 i 个字符转换成 word2 的前 j - 1 个字符，再插入当前缺少的 word2[j - 1]。

第三种，替换 word1[i - 1]：

dp[i - 1][j - 1] + 1

含义是：先把 word1 的前 i - 1 个字符转换成 word2 的前 j - 1 个字符，再把当前字符替换成目标字符。

三种操作中选择最小值：

dp[i][j] = Math.min(
  dp[i - 1][j] + 1,
  dp[i][j - 1] + 1,
  dp[i - 1][j - 1] + 1
);

所以完整转移方程是：

if (word1[i - 1] === word2[j - 1]) {
  dp[i][j] = dp[i - 1][j - 1];
} else {
  dp[i][j] = Math.min(
    dp[i - 1][j] + 1,
    dp[i][j - 1] + 1,
    dp[i - 1][j - 1] + 1
  );
}

3.`dp` 数组如何初始化

因为 dp[i][j] 表示前缀之间的转换，所以必须考虑空字符串。

第一列

dp[i][0] 表示把 word1 的前 i 个字符转换成空字符串。

只能不断删除，所以：

dp[i][0] = i;

例如：

"h"     -> ""  需要删除 1 次
"ho"    -> ""  需要删除 2 次
"hor"   -> ""  需要删除 3 次

第一行

dp[0][j] 表示把空字符串转换成 word2 的前 j 个字符。

只能不断插入，所以：

dp[0][j] = j;

例如：

"" -> "r"    需要插入 1 次
"" -> "ro"   需要插入 2 次
"" -> "ros"  需要插入 3 次

如果 word1 或 word2 本身就是空字符串，也可以直接通过第一行或第一列得到答案。

4. 确定遍历顺序

根据状态转移方程：

dp[i][j] 依赖 dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1]

也就是当前格子依赖：

正上方
左侧
左上方

所以按行从上到下、每一行从左到右遍历即可。

for (let i = 1; i <= word1.length; i++) {
  for (let j = 1; j <= word2.length; j++) {
    // 计算 dp[i][j]
  }
}

这样计算 dp[i][j] 时，它依赖的三个状态都已经计算完成。

5. 举例打印`dp` 数组

以 word1 = "horse"、word2 = "ros" 为例。

行表示 word1 的前缀，列表示 word2 的前缀：

`word1 \ word2`	`""`	`r`	`o`	`s`
`""`	0	1	2	3
`h`	1
`o`	2
`r`	3
`s`	4
`e`	5

填第 1 行：`"h"` 转换成`word2` 的前缀

dp[1][1] 表示 "h" 转换成 "r"。

h !== r，有三种选择：

删除：dp[0][1] + 1 = 2
插入：dp[1][0] + 1 = 2
替换：dp[0][0] + 1 = 1

取最小值，所以 dp[1][1] = 1。

继续计算这一行：

dp[1][2] = 2
dp[1][3] = 3

`word1 \ word2`	`""`	`r`	`o`	`s`
`""`	0	1	2	3
`h`	1	1	2	3
`o`	2
`r`	3
`s`	4
`e`	5

填第 2 行：`"ho"` 转换成`word2` 的前缀

dp[2][1] 表示 "ho" 转换成 "r"。

o !== r：

删除：dp[1][1] + 1 = 2
插入：dp[2][0] + 1 = 3
替换：dp[1][0] + 1 = 2

所以 dp[2][1] = 2。

dp[2][2] 表示 "ho" 转换成 "ro"。

最后一个字符都是 o，不需要操作：

dp[2][2] = dp[1][1] = 1;

dp[2][3] 表示 "ho" 转换成 "ros"。

o !== s：

删除：dp[1][3] + 1 = 4
插入：dp[2][2] + 1 = 2
替换：dp[1][2] + 1 = 3

所以 dp[2][3] = 2。

`word1 \ word2`	`""`	`r`	`o`	`s`
`""`	0	1	2	3
`h`	1	1	2	3
`o`	2	2	1	2
`r`	3
`s`	4
`e`	5

继续填完整张表

按照同样的规则继续计算：

`word1 \ word2`	`""`	`r`	`o`	`s`
`""`	0	1	2	3
`h`	1	1	2	3
`o`	2	2	1	2
`r`	3	2	2	2
`s`	4	3	3	2
`e`	5	4	4	3

最终答案是 dp[5][3] = 3，表示 "horse" 转换成 "ros" 最少需要 3 次操作。

一种对应的转换过程是：

horse -> rorse  将 h 替换成 r
rorse -> rose   删除第二个 r
rose  -> ros    删除 e

6. 代码实现

var minDistance = function (word1, word2) {
  const m = word1.length;
  const n = word2.length;

  // 需要多开一行一列，用来表示空字符串 ""。
  // 行数是 m + 1，对应 word1 的前 0 个字符到前 m 个字符。
  // 列数是 n + 1，对应 word2 的前 0 个字符到前 n 个字符。
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  // i 必须取到 m，因为 dp[m][0] 表示整个 word1 转换成空字符串。
  // 所以这里是 i <= m，而不是 i < m。
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;
  }

  // j 必须取到 n，因为 dp[0][n] 表示空字符串转换成整个 word2。
  // 所以这里是 j <= n，而不是 j < n。
  for (let j = 0; j <= n; j++) {
    dp[0][j] = j;
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1,
          dp[i][j - 1] + 1,
          dp[i - 1][j - 1] + 1
        );
      }
    }
  }

  return dp[m][n];
};

常见错误

不能用`fill` 直接创建二维数组

二维数组不能这样初始化：

const dp = new Array(m + 1).fill(new Array(n + 1).fill(0));

原因是：new Array(n + 1).fill(0) 只创建了一次，外层 fill 会把同一个数组引用填充到每一行。

也就是说，表面上看起来 dp 有很多行：

dp[0]
dp[1]
dp[2]

但这些行其实都指向同一个内部数组。

所以当你修改其中一行时：

dp[1][0] = 1;

其他行的第 0 列也会一起变化，因为它们本质上是同一个数组。

可以用下面的例子验证：

const dp = new Array(3).fill(new Array(4).fill(0));

dp[1][0] = 1;

console.log(dp);
// [
//   [1, 0, 0, 0],
//   [1, 0, 0, 0],
//   [1, 0, 0, 0]
// ]

这会直接破坏动态规划表，因为 dp[i][j] 本来应该表示一个独立状态，每一行必须互不影响。

正确写法是：

const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

这里的回调函数 () => Array(n + 1).fill(0) 会为每一行都重新创建一个新的数组，所以每一行都是独立的。

可以理解为：

错误写法：多行共用同一个数组
正确写法：每一行都有自己的数组

复杂度分析

时间复杂度：O(m * n)，其中 m 是 word1 的长度，n 是 word2 的长度。
空间复杂度：O(m * n)，需要二维数组保存所有状态。

ON THIS PAGE

#72.编辑距离

#1.dp 数组含义

#2. 确定状态转移方程

#当前字符相同

#当前字符不同

#3.dp 数组如何初始化

#第一列

#第一行

#4. 确定遍历顺序

#5. 举例打印dp 数组

#填第 1 行："h" 转换成word2 的前缀

#填第 2 行："ho" 转换成word2 的前缀

#继续填完整张表

#6. 代码实现

#常见错误

#不能用fill 直接创建二维数组

#复杂度分析