题目描述
思路解析
一句话答案：LeetCode 72 编辑距离的经典解法是二维动态规划：dp[i][j] 表示把 word1 的前 i 个字符变成 word2 的前 j 个字符的最少操作数，末位字符相同就直接继承左上角 dp[i-1][j-1]，不同则在删除、插入、替换三条来路里取最小再加一。时间 O(m·n)、空间 O(m·n)，可滚动压缩到 O(n)。
编辑距离这道题在问什么
给两个单词 word1 和 word2，每一步可以对 word1 插入、删除或替换一个字符，问把 word1 完全变成 word2 最少要几步。比如把 horse 变成 ros 只需 3 步。难点在于操作序列的自由度太大：先删哪个、在哪插、要不要替换，组合起来是天文数字，逐一枚举操作序列不可行。
为什么想到用两个前缀做状态
换个视角，别盯着操作序列，盯着两个字符串的末尾。想把 word1 的前 i 个字符变成 word2 的前 j 个字符，最优方案里对最后一个位置的处理只有四种可能：两个末位字符本来就相同，直接对上、不花操作；或者删掉 word1 的末字符；或者在末尾插入 word2 的末字符；或者把 word1 的末字符替换成 word2 的末字符。
无论选哪种，剩下的部分都是一个更短前缀对更短前缀的同样问题。也就是说，「word1 前 i 位变 word2 前 j 位的最少步数」只依赖三个更小的子问题，与前面具体怎么变过来的无关——这就是无后效性，二维动态规划的地基。
dp 表怎么定义，首行首列为什么是 0 到 n
定义 dp[i][j] 为把 word1 的前 i 个字符变成 word2 的前 j 个字符的最少操作数，答案就是右下角 dp[m][n]。表比字符串各多一行一列，用来表达空串。
边界先铺好：dp[0][j] = j，空串要变出长度 j 的前缀，只能一个个插入，恰好 j 步；dp[i][0] = i，要把长度 i 的前缀变成空串，只能一个个删光。左上角 dp[0][0] = 0，空串变空串不用动。忘了这两条边界是本题最常见的错误，后面每一格都建立在它们之上。
三条来路为什么分别对应删、插、替换
填内部格 dp[i][j] 时，先比较 word1 第 i 个字符和 word2 第 j 个字符。相同时这一对天然对上，dp[i][j] = dp[i-1][j-1]，直接抄左上角，一步不花——注意相同时不能加一，多加就把答案算大了。
不同时三选一取最小再加一：dp[i-1][j] + 1 是删——先把 word1 少末位的前缀变好，再删掉这个多余字符；dp[i][j-1] + 1 是插——先变出 word2 少末位的前缀，再补插上它的末字符；dp[i-1][j-1] + 1 是替换——两边各退一位先对齐，再把这对不同的字符换掉。三条路覆盖了处理末位的全部方式，取最小者即最优，方向别记混：上是删、左是插、左上是替换。
复杂度多少，空间怎么优化
时间复杂度 O(m·n)，m、n 是两个单词的长度：整张表每格填一次，每次只做常数次比较。空间 O(m·n) 存全表；由于每格只依赖上一行和本行左边，可用滚动数组只保留一行、再拿一个变量暂存左上角值，空间降到 O(n)。
编辑距离（也叫 Levenshtein 距离）是拼写纠错、DNA 序列比对、模糊搜索的底层度量，这张「前缀对前缀」的二维表也是最长公共子序列等一整族双串动态规划的通用骨架，值得吃透。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条转移，下面每个内部格都在套它。
左上角：空串变空串，不用动，填 0。下面先把「免费基准」首行首列铺好。
首行：word1 是空串，要变出 "r" 只能插入 1 次 → dp[0][1]=1。
首行：word1 是空串，要变出 "ro" 只能插入 2 次 → dp[0][2]=2。
首行：word1 是空串，要变出 "ros" 只能插入 3 次 → dp[0][3]=3。
首列：word2 是空串，把 "h" 删光要删 1 次 → dp[1][0]=1。
首列：word2 是空串，把 "ho" 删光要删 2 次 → dp[2][0]=2。
首列：word2 是空串，把 "hor" 删光要删 3 次 → dp[3][0]=3。
首列：word2 是空串，把 "hors" 删光要删 4 次 → dp[4][0]=4。
首列：word2 是空串，把 "horse" 删光要删 5 次 → dp[5][0]=5。
'h'≠'r'，三条路各 +1：删上面=2、增左边=2、改左上=1，挑最小。
取最小走「改」：dp[1][1]=1+0=1。
'h'≠'o'，三条路各 +1：删上面=3、增左边=2、改左上=2，挑最小。
取最小走「改」：dp[1][2]=1+1=2。
'h'≠'s'，三条路各 +1：删上面=4、增左边=3、改左上=3，挑最小。
取最小走「改」：dp[1][3]=1+2=3。
'o'≠'r'，三条路各 +1：删上面=2、增左边=3、改左上=2，挑最小。
取最小走「改」：dp[2][1]=1+1=2。
'o' 和 'o' 一样，这俩字母天然对上、不用动，直接抄左上角 1。
落子：dp[2][2]=1（继承左上角）。
'o'≠'s'，三条路各 +1：删上面=4、增左边=2、改左上=3，挑最小。
取最小走「增」：dp[2][3]=1+1=2。
'r' 和 'r' 一样，这俩字母天然对上、不用动，直接抄左上角 2。
落子：dp[3][1]=2（继承左上角）。
'r'≠'o'，三条路各 +1：删上面=2、增左边=3、改左上=3，挑最小。
取最小走「删」：dp[3][2]=1+1=2。
'r'≠'s'，三条路各 +1：删上面=3、增左边=3、改左上=2，挑最小。
取最小走「改」：dp[3][3]=1+1=2。
's'≠'r'，三条路各 +1：删上面=3、增左边=5、改左上=4，挑最小。
取最小走「删」：dp[4][1]=1+2=3。
's'≠'o'，三条路各 +1：删上面=3、增左边=4、改左上=3，挑最小。
取最小走「改」：dp[4][2]=1+2=3。
's' 和 's' 一样，这俩字母天然对上、不用动，直接抄左上角 2。
落子：dp[4][3]=2（继承左上角）。
'e'≠'r'，三条路各 +1：删上面=4、增左边=6、改左上=5，挑最小。
取最小走「删」：dp[5][1]=1+3=4。
'e'≠'o'，三条路各 +1：删上面=4、增左边=5、改左上=4，挑最小。
取最小走「改」：dp[5][2]=1+3=4。
'e'≠'s'，三条路各 +1：删上面=3、增左边=5、改左上=4，挑最小。
取最小走「删」：dp[5][3]=1+2=3。
右下角 dp[5][3]=3，就是把 "horse" 改成 "ros" 的最少步数。
边界先想清。
两个高频追问。
参考代码
def minDistance(w1, w2): m, n = len(w1), len(w2) dp = [[0]*(n+1) for _ in range(m+1)] for j in range(n+1): dp[0][j] = j for i in range(m+1): dp[i][0] = i for i in range(1, m+1): for j in range(1, n+1): if w1[i-1] == w2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]复杂度
- 时间：O(m·n)，填满整张表
- 空间：O(m·n)，可滚动优化到 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么三条来路对应删/增/改？
追问怎么把空间降到 O(n)？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
戳气球
LeetCode 312 · 困难 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题