编辑距离

编辑距离（Levenshtein 距离）问的是：把字符串 s 改成 t，最少需要几次操作？每一次操作可以是：

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

经典例子 kitten → sitting 的距离是 3（替换 k→s、替换 e→i、末尾插入 g）。

状态与转移

定义二维 DP：

dp[i][j] = 把 s 的前 i 个字符变成 t 的前 j 个字符所需的最少操作数

边界：

• dp[0][j] = j（空串到 j 个字符要插入 j 次）
• dp[i][0] = i（i 个字符到空串要删除 i 次）

转移：

• 如果 s[i-1] == t[j-1]，免费继承：dp[i][j] = dp[i-1][j-1]
• 否则取三个邻居最小值 +1：
  • 删除：dp[i-1][j] + 1
  • 插入：dp[i][j-1] + 1
  • 替换：dp[i-1][j-1] + 1

复杂度

• 时间：O(m·n)
• 空间：O(m·n)（实际可以滚动数组压到 O(min(m, n))）

在动画里看什么

• 表格顶部是目标串 t（含一个 ε 空前缀），左侧是源串 s
• 深蓝：当前正在计算的格子；白色：已算出的值；灰色：还没算
• 算完后，暖红单元格描出从 dp[m][n] 回溯到 dp[0][0] 的路径，对应一种具体的编辑方案