编辑距离LeetCode 72详解：二维DP推导与一维空间优化

我第一次做 LeetCode 72 编辑距离是在刷热门 100 题的时候。当时二维 DP 的题解我能看懂但一关上题解自己写就全乱三个转移方向记住了却不知道它们到底在干什么dp 表能画出来但画完对着代码又觉得哪里不对。后来花了一晚上把状态转移从“背公式”变成“推结论”才发现这道题真正的门槛不在代码而在 dp[i][j] 的含义。这篇文章我会按这个顺序来讲先理解编辑距离本身再完整推一遍二维 DP 的转移方程并给出可复现代码然后重点拆解一维空间优化里最容易出错的左上角保存时机最后用两三个同类题把这套思路固化成肌肉记忆。适合正在刷 DP 题、看懂了题解但独立写不出代码的读者。1. 先看问题编辑距离到底在衡量什么1.1 三种操作是什么以及一个经典例子先放题目本身给定两个字符串 word1 和 word2可以把 word1 通过插入、删除、替换字符变成 word2求最少操作次数。这里的“操作”都是字符级别的插入在 word1 的任意位置加一个字符。删除删掉 word1 中任意一个字符。替换把 word1 中某个字符替换成另一个字符。官方的示例 1 是 word1 horseword2 ros答案是 3。典型的转换路径是这样走出来的先把 h 替换成 r得到 rorse再删掉第二个 r得到 rose最后删掉末尾的 e得到 ros。三步每步只动一个字符。示例 2 是 word1 intentionword2 execution答案是 5。这个周期更长删除 t再把 i 替换成 e、n 替换成 x、n 替换成 c最后插入一个 u共 5 次操作。看这两个例子能发现插入和删除会改变字符串长度这就导致了下一个问题大多数人第一反应的逐字符匹配思路在这里会失效。1.2 为什么“逐字符匹配”的直觉会失效很多初学者一看到字符串转换就想用两个指针逐位对齐从左往右扫一遍遇到不同的字符就替换。这个思路在编辑距离里会立刻碰壁因为插入和删除会让两个字符串的位置关系产生“错位”。拿 horse 到 ros 来说你很难说清楚 horse 的第 2 个字符 o 对应 ros 的哪个字符第 3 个字符 r 又对应 ros 的哪个字符。实际转换过程里o 被保留了下来r 从原字符串的第 3 位被“移动”到了目标串的第 1 位——这种移动其实是通过删除和插入实现的而不是真的有一个“移动”操作。这就是为什么编辑距离要引入二维 DP两个串之间没有一个固定的位置对应关系所以不能用一维的匹配思路去解。二维 DP 的做法是把问题切成子问题把“word1 的前 i 个字符变成 word2 的前 j 个字符”当成一个独立的状态。这样不管字符怎么错位子问题都是有限且可递推的。这也是所有字符串 DP 题里最基础的建模方式。2. 状态定义与转移方程推导里最容易卡住的三个地方2.1 dp[i][j] 的含义只看前 i 个和前 j 个字符直接定义dp[i][j] 表示 word1 的前 i 个字符word1[0:i]转换成 word2 的前 j 个字符word2[0:j]所需的最少操作次数。注意两个细节。第一“前 i 个”和“前 j 个”是子问题的边界后面的字符根本不参与计算。第二dp 表不是直接从字符串下标对齐开始的而是从 0 开始的dp[0][j] 表示空串到 word2 前 j 个字符的编辑距离dp[i][0] 表示 word1 前 i 个字符到空串的编辑距离。为什么可以只看前缀因为编辑操作只会影响局部字符。如果你已经确定了要把 word1 的前 i 个字符变成 word2 的前 j 个字符那么前面的字符在后续操作里不会再被修改。这保证了无后效性也让子问题能够独立递推。很多人画表时总觉得“后面还有字符怎么办”其实在子问题里没有后面只有当前前缀。2.2 三种转移路径怎么从“最后一次操作”反推这是整道题最核心的部分。与其死记 min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1不如想清楚每一个方向到底在干什么。我们假设要把 word1 前 i 个字符变成 word2 前 j 个字符倒过来想最后一次操作是什么最后一次操作是删除。删除的一定是 word1 的第 i 个字符。那么在删除之前word1 的前 i-1 个字符必须已经变成了 word2 的前 j 个字符即 dp[i-1][j]。然后再删掉第 i 个字符操作次数加 1所以 dp[i][j] dp[i-1][j] 1。最后一次操作是插入。插入的一定是 word2 的第 j 个字符。因为在插入之前word1 的前 i 个字符已经变成了 word2 的前 j-1 个字符也就是 dp[i][j-1]。此时 word1 已经能和 word2 前 j-1 个字符对齐只差最后一个字符再插一次就完成所以 dp[i][j] dp[i][j-1] 1。最后一次操作是替换。把 word1 的第 i 个字符替换成 word2 的第 j 个字符。替换前word1 前 i-1 个字符必须已经变成 word2 前 j-1 个字符即 dp[i-1][j-1]再替换一次所以 dp[i][j] dp[i-1][j-1] 1。三个方向取最小值就是当前状态的最优解dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1。还有一个特殊情况如果 word1[i-1] 和 word2[j-1] 恰好相等那么这两个字符不用做任何操作直接继承前缀对齐的结果 dp[i-1][j-1] 就行不需要加 1。这个分支是编辑距离题一个容易忽略、但必须处理的点。2.3 替换和“删除插入”的区别有一个疑问经常出现替换一步就能让两个字符对齐代价是 1删除加插入需要两步代价是 2。那为什么转移方程还要保留删除和插入两个方向原因在于 dp[i-1][j] 和 dp[i][j-1] 代表的子问题状态不同。举个例子dp[5][0] 表示把 horse 变成空串这个状态只能通过连续 5 次删除到达替换在这里没有任何意义dp[0][3] 表示把空串变成 ros只能通过 3 次插入到达。也就是说存在的字符数量差异决定了有些路径必须靠删除或插入来补齐替换并不能永远替代它们。从另一个角度理解替换解决的是“两个串长度相同但字符不同”的情况删除解决的是“word1 比 word2 长”的情况插入解决的是“word1 比 word2 短”的情况。三种操作覆盖三类不同的差距所以三个转移方向缺一不可。这个认识对后面做 583、1143 等变种题也很有帮助因为它们其实就是手动砍掉某些操作后的退化版本。3. 二维DP实现与常见踩坑3.1 初始化的含义空串是 DP 的天然底边二维表的大小是 (m1) × (n1)比字符串长度各多一行一列。为什么非要多一行一列因为 dp[0][0] 表示两个空串dp[0][j] 表示 word1 为空串时的情况dp[i][0] 表示 word2 为空串时的情况。空串是 DP 的底边没有它递推就没有起点。dp[i][0] iword1 的前 i 个字符要变成空串只能把 i 个字符全部删除。删除 i 次。dp[0][j] j空串要变成 word2 的前 j 个字符只能连续插入 j 个字符。插入 j 次。这个初始化很多人会漏掉 dp[i][0] 那列或者写反。其实不用死记只要想清楚“空串到非空只能插入非空到空串只能删除”就不会错。另一个常见问题是索引偏移dp[i][j] 对应的是 word1 的前 i 个字符和 word2 的前 j 个字符所以判断当前两个字符是否相等时用的是 word1[i-1] 和 word2[j-1]而不是 word1[i] 和 word2[j]。第一次写的人十有八九会在这里 bug。3.2 完整代码与 horse - ros 的 dp 表验证二维版本的代码很直接按上面的推导写就行def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i - 1] word2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) 1 return dp[m][n]拿官方例子 horse - ros 验证一遍。填出来的 dp 表如下dpros0123h1123o2212r3222s4332e5443最终 dp[5][3] 3和答案一致。看表里 dp[3][3] 2表示 hor 到 ros 最少需要 2 步做法是把 h 替换成 r把 r 替换成 s代价 2。这个表格建议自己重新填一遍填到一半就能感觉到三个方向的含义比盯着代码看要有效得多。3.3 写二维DP时最常见的两个失误我见过很多人在这个题上翻车归纳下来主要是两种第一种是初始化写错或漏写。第一行第一列一旦全填 0后面的递推结果就全部偏移了而且很难通过肉眼看出来因为小样例可能恰好碰对。建议写完代码后先用两个极端用例验证word1 为空、word2 为空。第二种是字符相等时也走 min(...) 1 的分支。这样做虽然结果通常也对因为三个方向的代价都不会小于 dp[i-1][j-1]但会把你自己的思路绕弯面试被追问“为什么相等时不加 1”时容易讲不清楚。正确做法是相等时直接继承左上角语义最干净。另外循环里一定要保持 i 对应 word1j 对应 word2。我见过有人把判断写成 word1[j-1] word2[i-1]短样例碰巧过长样例就崩。定义清楚两个维度的含义比急着优化代码更重要。4. 一维空间优化滚动数组的核心不是省一维而是保存左上角4.1 依赖分析为什么只需要一行观察 dp[i][j] 的依赖方向它只用到三个格子正上方 dp[i-1][j]、左边 dp[i][j-1]、左上角 dp[i-1][j-1]。这说明计算当前行时只需要上一行的数据上上一行完全可以丢掉。所以我们不需要维护整个 (m1) × (n1) 的矩阵只需要一个长度为 n1 的一维数组不断滚动更新。滚动数组的难点在于“覆盖”这两个字。一维数组里dp[j] 在更新前存的是上一行的值 dp[i-1][j]更新后就变成了本行的 dp[i][j]。而你下一轮计算 dp[j1] 时还需要用到 dp[i-1][j] 作为它的左上角。如果这个旧值已经被覆盖掉了结果就会错。所以一维优化的本质不是省那一维而是想清楚每个变量的保存时机。4.2 一维代码实现与 left_up 的保存时机看下面的代码重点注释我已经标出来了def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) # 让 word2 更短dp 数组更小编辑距离在交换两个串后结果不变 if m n: word1, word2 word2, word1 m, n n, m # dp[j] 表示 dp[0][j]即空串到 word2 前 j 个字符的编辑距离 dp [j for j in range(n 1)] for i in range(1, m 1): left_up dp[0] # 上一行的 dp[0]即 dp[i-1][0] dp[0] i # 当前行的 dp[i][0] i for j in range(1, n 1): up dp[j] # dp[i-1][j]正上方 left dp[j - 1] # dp[i][j-1]左边 if word1[i - 1] word2[j - 1]: dp[j] left_up # 继承左上角 else: dp[j] min(left_up, up, left) 1 left_up up # 下一轮 j1 的左上角就是当前 j 的 up return dp[n]来手动走一遍 i 1处理 word1 的第 0 个字符的情况。初始化 dp [0, 1, 2, 3]。进入循环后 left_up dp[0] 0这个 0 就是 dp[0][0]。然后 dp[0] 更新为 1对应 dp[1][0]。j 1 时up dp[1] 1上一行的 dp[0][1]left dp[0] 1当前行的 dp[1][0]left_up 0dp[0][0]。字符 h 和 r 不相等dp[1] min(0, 1, 1) 1 1。然后 left_up up 1。j 2 时up dp[2] 2上一行的 dp[0][2]left dp[1] 1刚更新的 dp[1][1]left_up 1dp[0][1]。字符 h 和 o 不相等dp[2] min(1, 2, 1) 1 2。然后 left_up up 2。j 3 时up dp[3] 3left dp[2] 2left_up 2dp[0][2]。dp[3] min(2, 3, 2) 1 3。这一轮结束后 dp [1, 1, 2, 3]正好就是二维表里 h 那一行。可以看到关键是 left_up 这个变量它在循环开始时先保存 dp[0] 的旧值在后面每次循环里扮演“左上角”循环结束前再更新为当前位置的 up为下一轮做准备。4.3 为什么可以交换 word1 和 word2代码里做了一件事如果 m n就把 word1 和 word2 交换让最终 dp 数组的长度是 min(m, n)。这里需要解释一下合法性。编辑距离的三个操作是对称的word1 删除一个字符等价于 word2 插入一个字符word1 插入一个字符等价于 word2 删除一个字符替换在两个方向上等价。因此把 word1 转换成 word2 的最少操作数和把 word2 转换成 word1 的最少操作数完全一样。既然结果对称谁当第一维谁当第二维就无所谓于是我们可以把较短的串固定为第二维减少一维数组的长度。这是个纯常数优化但对空间敏感的场景有意义。边界情况也顺手验证一下。两个空串时循环不执行返回 dp[0] 0。word1 为空、word2 abc 时交换后 word1 abc、word2 dp [0]三轮循环后返回 dp[0] 3答案正确。这两个极端用例建议每次写完滚动数组都跑一遍能挡住大部分低级错误。还有一个常见错误字符相等时如果错误地把 dp[j] 写成 min(left_up, up, left) 1结果会偏大。因为相等情况下多花一次操作永远是浪费的。这个分支不要合并写清楚。5. 实测对比与同类题迁移5.1 二维和一维的实际差异以及面试取舍很多读者会问LeetCode 72 的字符串长度最多 500二维 DP 在内存上是完全够用的为什么还要学一维优化我的看法是不是为了省那点内存而是要理解滚动数组这一整套思维方式因为它在更多字符串 DP 题里会出现。维度二维DP一维DP空间复杂度O(mn)O(min(m, n))时间复杂度O(mn)O(mn)写起来容易程度直观适合学习阶段需要维护 left_up易错面试印象能过但不算亮点能体现对空间优化的理解实际跑起来500 × 500 的二维表在 Python 里大概需要 10MB 左右的内存LeetCode 完全是能接受的。但我在本地测试过当字符串长度到 2000 以上时二维数组的内存开销在 Python 里会长得很快这时一维版本的优势就明显了。面试中比较稳的顺序是先写出二维版本把转移方程讲清楚再主动补一句“空间上可以滚动到 O(n)”然后把一维代码完整写出来。这比一上来就闷头写滚动数组更容易给人留下好印象。5.2 这套递推还能解哪些题从编辑距离到 583、1143、44编辑距离这套状态定义和滚动数组技巧可以迁移到好几道经典题LeetCode 583 两个字符串的删除操作。这道题只允许删除不允许插入和替换。转移方程退化成如果字符相等取 dp[i-1][j-1]否则取 min(dp[i-1][j], dp[i][j-1]) 1。做完 72 再回来写 583 会非常快因为它就是编辑距离砍掉两个操作后的样子。LeetCode 1143 最长公共子序列。转移方程长得很像字符相等时 dp[i-1][j-1] 1不相等时取 max(dp[i-1][j], dp[i][j-1])。它和编辑距离之间有一个有意思的关系如果限定只能用插入和删除编辑距离等于 m n - 2 × LCS。理解这个关系会比单独背 1143 的代码更有收获。LeetCode 44 通配符匹配。这是编辑距离的扩展版状态定义和滚动数组完全通用只是转移时多了*的特殊处理。你不要把它当成一道新题它就是“编辑距离框架 特殊字符规则”。还有 LeetCode 97 交错字符串虽然题名看起来不同但还是二维字符串 DP 的套路。学到后面你会发现字符串 DP 题的核心敲门砖就是编辑距离这道题。什么“子序列”“交错”“匹配”本质都是把两个前缀之间的关系定义清楚然后从三个方向里选最优。我自己刷完这套题之后最大的感受是二维 DP 最值得花时间的不是背转移方程而是把 dp[i][j] 的含义和三个方向在做什么用自己的话讲清楚。等到讲明白了一维优化只是顺水推舟。如果这篇题解对你有帮助建议先别抄代码拿 horse 到 ros 在纸上把 dp 表填一遍填到一半你大概率就能感觉到转移方向是怎么自己冒出来的。最后留一个我自己的小习惯遇到任何字符串 DP 题先问自己三个问题——状态表示什么这一格能从哪些格子来初始化怎么定这三件事想清楚代码只是翻译的过程。