编辑距离
动态规划 · 字符串 · Levenshtein 距离
把一个词改成另一个词，最少几步
把 SAT 改成 SUN，每步可以插入、删除或替换一个字符，最少要几步？这个「最少编辑次数」就是编辑距离，是拼写纠错、文本 diff、DNA 序列比对的核心。逐一枚举改法会爆炸，动态规划能优雅解决。
用一张表填出答案
设 dp[i][j] = 把「源串前 i 个字符」变成「目标串前 j 个字符」的最少编辑次数。边界：把空串变成 j 个字符要插 j 次（第 0 行 = 0,1,2,…）；把 i 个字符变成空串要删 i 次（第 0 列同理）。
然后逐格填——每个 dp[i][j] 只看它的三个邻居：左上（都不动/替换）、上（删）、左（插）。若当前两个字符相同，不用编辑，直接取左上；若不同，取三个邻居的最小值 + 1。填到右下角就是答案。
下面固定 SAT → SUN。点「下一步」逐格看：当前格琥珀环，它依赖的邻居格黄色高亮，字符相同（绿）取左上、不同取 1+min 三邻——填入即变绿。走到底，右下角 = 2（SAT→SUN：A→U、T→N 两次替换）。右侧代码随每一步同步高亮。
| ∅ | S | U | N | |
|---|---|---|---|---|
| ∅ | 0 | 1 | 2 | 3 |
| S | 1 | |||
| A | 2 | |||
| T | 3 |
边界：空串变成前 j 个字符需插 j 次（第 0 行）；前 i 个变成空串需删 i 次（第 0 列）
1function editDistance(a: string, b: string): number {
2 const m = a.length, n = b.length;
3 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
4 for (let j = 0; j <= n; j++) dp[0][j] = j;
5 for (let i = 0; i <= m; i++) dp[i][0] = i;
6 for (let i = 1; i <= m; i++) {
7 for (let j = 1; j <= n; j++) {
8 if (a[i - 1] === b[j - 1]) {
9 dp[i][j] = dp[i - 1][j - 1];
10 } else {
11 dp[i][j] =
12 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
13 }
14 }
15 }
16 return dp[m][n];
17}
源串SAT
目标串SUN
1 / 11
这就是动态规划的精髓：大问题拆成子问题、子问题的解填进表格、后面的直接查表复用。每格 O(1)、共 O(m·n) 格，远快于枚举。递推式「相同取左上、不同 1+min 三邻」正是把「插/删/替」三种操作对应到三个邻居方向。
编辑距离在哪里用
拼写纠错 / 模糊搜索：找与输入编辑距离最小的候选词。
文本 diff / 版本对比：Git、编辑器的差异算法都由它变体而来。
生物信息：DNA / 蛋白质序列比对。它是二维矩阵 DP 的最经典范例。
文本 diff / 版本对比：Git、编辑器的差异算法都由它变体而来。
生物信息：DNA / 蛋白质序列比对。它是二维矩阵 DP 的最经典范例。
同样「填矩阵」的动态规划还有很多——最长公共子序列、背包等，都是在一张表上按递推式逐格填。想看另一种「矩阵 DP」，可回看 Floyd 多源最短路（距离矩阵逐点中转）。