编辑距离
编辑距离是把一个字符串变成另一个所需的最少单字符插入、删除和替换次数。Levenshtein 动态规划比较每对前缀，在表中保存最小成本，再回溯得到一份实际编辑步骤。
拼写检查、模糊搜索、OCR 修正和记录去重可使用这类距离。本课每次编辑成本为 1；实际应用可按任务调整成本。
每格都决定如何处理两个前缀的末尾：删除消耗源字符，插入消耗目标字符，替换同时消耗两者；相同字符则免费保留。
编辑距离如何工作
dp[i][j] 表示把 source[:i] 转成 target[:j] 的最小成本。空前缀也占一行一列：把 i 个字符删为空需要 i 次，所以 dp[i][0] = i；从空插入 j 个字符需要 j 次，所以 dp[0][j] = j。
比较 source[i - 1] 与 target[j - 1]。相同就免费保留：
dp[i][j] = dp[i - 1][j - 1]
不同时，最后一步有三种候选：
- 删除源末字：
dp[i - 1][j] + 1。 - 插入目标末字：
dp[i][j - 1] + 1。 - 替换这对字符：
dp[i - 1][j - 1] + 1。
取最小值。邻居已是更小前缀问题的最优解。若完整最优方案以某项操作结束，去掉该步就留下对应邻居问题；邻居若还有更便宜解，完整方案也能更便宜，与最优假设矛盾。因此三种结尾的最小值给出当前格的全局最优。
右下角只给距离。回溯中，相同字符的对角移动记免费 keep，不同字符的对角记 replace，向上记 delete，向左记 insert。平局时本课优先 replace，再 insert，再 delete，选择一份可复现的最优脚本。
逐步演示
默认把 KITTEN 变成 SITTING。
- 左边界填
0, 1, 2, ..., 6，上边界填0, 1, 2, ..., 7，分别是纯删除、纯插入的答案。 - 第一格比较 K 与 S。删除、插入都需 2，替换 K→S 只需 1，取对角替换值 1。
- 按行继续。第一个 I 遇到 I 时免费复制左上值；不同字符时，面板同时显示删除、插入、替换候选，再提交最小值。平局可改变脚本，不改变距离。
- 42 个内部格填完，右下角为 3，操作条仍空，因为还没恢复步骤。
- 从
(6, 7)回溯：先向左记insert G，再 keep N、replace E→I、keep 两个 T 和 I，最后 replace K→S。 - 回溯从右向左填固定位置，正序脚本为
replace K→S、keep I、keep T、keep T、replace E→I、keep N、insert G。恰好三项成本 1，与dp[6][7] = 3一致。 - 从左到右重放脚本，消耗全部源字符，写出
SITTING，验证最小成本确实可达到。
为什么逐位置比较会失败
shift-trap 中，ABCDEF 与 BCDEFG 的六个对应位置全不同，但删开头 A、插末尾 G 只需 2 次。一次编辑可以让整个后缀重新对齐，不能只按相同位置计差异。
时间与空间复杂度
| 工作 | 成本 |
|---|---|
| 填 DP 表 | O(m × n) 时间 |
| 保存完整表 | O(m × n) 空间 |
| 回溯与重放一份脚本 | O(m + n) 时间 |
m、n 为源和目标长度，二维表常是首先遇到的规模限制。只需分数或阈值判断，可保留两行或正确更新的一行，用 O(min(m, n)) 空间。需要实际修正时保留全表或等价前驱信息。只接受距离不超过小值 k 时，还可用带状 DP 跳过远离对角线的格子。
边界情况
- 两者都空，距离 0。
- 源为空，每个目标字符一次插入。
empty-source将""变成 CAT，共三次。 - 目标为空，每个源字符一次删除。
- 相同字符串沿免费对角线，距离 0。
- 重复字符与平局可产生多份同成本最优脚本。
- 标准 Levenshtein 不把交换当一步：CA→AC 的距离为 2。
- 每串最多八个大写字母，只为保持网格可读，不是算法限制。
常见错误
- 基础行列全填 0。 它们保存插入和删除次数，不是空占位。
- 匹配仍加一。 相同末字免费复制左上成本。
- 回溯中插删反了。 向左插入目标字符，向上删除源字符。
- 只选眼前最便宜编辑。 要比较前缀状态，逐位置贪心会错过重新对齐。
- 误算汉明距离。 汉明距离只逐位置比较等长串，不处理插删。
- 需要脚本却只读右下角。 数字给最优成本，回溯才给达到它的操作序列。