最小编辑距离

最小编辑距离研究：把字符串 $X$ 变成 $Y$，至少需要多少次编辑。经典 Levenshtein 距离允许插入、删除和替换，每次代价为 1。

1. 状态从两个前缀出发

令

$$dp[i][j]=X[1..i]\text{ 变成 }Y[1..j]\text{ 的最小代价}.$$

边界很直观：

$$dp[i][0]=i,\qquad dp[0][j]=j.$$

非空字符串变成空串只能逐个删除；空串变成非空字符串只能逐个插入。

2. 状态转移

若 $x_i=y_j$，末尾无需编辑：

$$dp[i][j]=dp[i-1][j-1].$$

若不同，最后一步有三种可能：

$$dp[i][j]=1+\min\begin{cases} dp[i-1][j],&\text{删除 }x_i,\\ dp[i][j-1],&\text{插入 }y_j,\\ dp[i-1][j-1],&\text{把 }x_i\text{ 替换为 }y_j. \end{cases}$$

合写时可令替换代价 $[x_i\ne y_j]$。

3. 如何理解“插入”的方向

$dp[i][j-1]\to dp[i][j]$ 表示前 $i$ 个源字符已经变成 $Y[1..j-1]$，再插入 $y_j$。这里源串下标不动、目标串下标减少一个。

最常见的错误是只背“左、上、左上”，却忘了它们分别代表哪种动作。应始终从“最后一步做了什么”推导。

4. 例子：kitten 到 sitting

一条最优编辑序列是：

1. kitten 中 k 替换为 s；
2. sitten 中 e 替换为 i；
3. sittin 末尾插入 g。

所以距离为 3。

5. 正确性思路

取一条最优编辑序列，观察其最后一步。最后一步必然属于匹配、插入、删除、替换之一；去掉最后一步后，前面的操作也必须是相应前缀子问题的最优解，否则可以替换成更短方案，进而改进原答案。

这就是最优子结构。不同编辑序列可能到达同一对前缀，则形成重叠子问题。

6. 恢复编辑序列

保留二维表，从 $(m,n)$ 反向查看当前值来自哪个前驱：

• 左上且字符相同：匹配，不产生操作；
• 左上加替换代价：替换；
• 上方加删除代价：删除；
• 左方加插入代价：插入。

若多个前驱同为最优，最优编辑序列不唯一。回溯时记录的动作顺序也要反转。

7. 加权编辑距离

实际问题中三种操作未必同价。将递推式中的 1 改成 $c_{del}(x_i)$、$c_{ins}(y_j)$ 和 $c_{sub}(x_i,y_j)$ 即可。OCR、语音识别、生物序列比对通常会根据混淆概率设计代价。

如果允许交换相邻字符，还要加入新的状态来源，形成 Damerau–Levenshtein 距离；不能偷偷把交换当作一次经典编辑。

8. 复杂度与优化

标准算法时间 $O(mn)$、空间 $O(mn)$。只求距离时可滚动数组降到 $O(\min(m,n))$；要回溯操作序列则通常保留整表或采用分治恢复。