题目
给你两个单词
word1 和
word2，返回将
word1 转换成
word2 所使用的
最少操作数，可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: horse -> rorse (替换 h 为 r)
rorse -> rose (删除 r)
rose -> ros (删除 e)
LC 72 是腾讯 DP 方向的经典压轴：先让你写出二维推演，然后几乎必然会追问一句「空间能压到 O(n) 吗」。这一问才是分水岭 —— 压缩本身不难，难在
三个依赖方向里有一个会被你自己覆盖掉。
一、核心洞察：两个锚，前缀对前缀
上一篇
LC 300 说动态规划的破局动作是「给状态加一个锚」，那道题的锚是
dp[i] = 以 nums[i] 结尾。编辑距离的锚形状完全不同 ——
它一次要下两个：
dp[i][j] = 把 a 的前 i 个字符 变成 b 的前 j 个字符 的最少操作数（a = word1，b = word2）。
为什么必须是「前缀」而不能是「以
i 结尾」？因为编辑操作会在
任意位置增删字符：把
horse 变成
ros 的最后一步是删掉
e，这一步关心的不是「以哪个字符结尾」，而是「两个串各自还剩多长」。
只有前缀长度这一对数字，才能完整描述「接下来还要处理的现场」 —— 这就是子序列型与双串型的分岔点。
两个锚一立，转移只需要看一件事：
最后一对字符 a[i-1] 和 b[j-1] 怎么处理。不管中间那
i-1 对
j-1 对字符多么纠缠，它们都被锚进了
dp[...][...] 里，不再需要展开。
初始化也不再是「填 0」：
dp[0][j] = j（空串长成
b 的前
j 个字符，只能一个一个插）、
dp[i][0] = i（
a 的前
i 个字符缩成空串，只能一个一个删）。
第一行和第一列不是凑数，它们就是语义本身 —— 九、会看到把它们填成 0 的代码在官方样例上直接错成 2。
二、拆解：三种操作 = 三个邻居
dp[i][j] 的最后一步只可能是三种收尾之一，而
每一种恰好对应表里的一个邻居：
于是：
def minDistance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
a, b = list(word1), list(word2)
# dp[i][j]：a 的前 i 个字符 变成 b 的前 j 个字符 的最少操作数
dp = [[0] * (n + 1) for _ in range(m + 1)]
for j in range(n + 1):
dp[0][j] = j # 空串长成 b 的前 j 个字符：插入 j 次
for i in range(1, m + 1):
dp[i][0] = i # a 的前 i 个字符缩成空串：删除 i 次
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # 相同：这一对免费
else:
dp[i][j] = 1 + min(
dp[i - 1][j - 1], # 替换：把 a[i-1] 改成 b[j-1]
dp[i - 1][j], # 删除：删掉 a[i-1]
dp[i][j - 1], # 插入：补一个 b[j-1]
)
return dp[m][n]
喜欢紧凑的可以写成一行 ——
dp[i][j] = min(dp[i-1][j-1] + (a[i-1] != b[j-1]), dp[i-1][j] + 1, dp[i][j-1] + 1)，字符相同时第一项自然不收钱。
一个值得专门说的事实：把「插入」和「删除」这两个标注互换，答案一个数字都不会变。 因为
min 覆盖的是同一个集合
{对角, 上方, 左方}，谁叫什么名字不影响取最小值（我用脚本对
horse -> ros 逐格比对过，两张表完全相同）。它唯一能暴露的地方，是你被追问「把操作序列打出来」的时候 —— 标注反了，重建出来的操作序列就是错的。
数值层面无害、重建层面致命，这是这类「对称转移」题的共同陷阱。
三、动画怎么看
动画是一张
(m+1) x (n+1) 的表，逐格点亮。颜色语法只有一条：
三种操作 = 三个邻居 = 三种颜色。
- 横幅：左边「在填哪个格子」，中间本帧结论（相同抄对角 / 取哪种操作），右边本格的值；
- 行列头：
i=0 和 j=0 那行/列显示 ""，它们是边界，画成灰底虚线 —— 不是算出来的；
- 格子：还没算到的画虚线空壳；本帧正在填的格子亮金底，操作代号标在格子里（
sub 替换 / del 删除 / ins 插入 / ok 相同免费）；
- 三个邻居：填本格的瞬间，对角、上方、左方同时被点亮成各自的颜色，胜出的那个再套一圈金环；
- 字符相同的帧：只有对角被点亮，上方和左方直接压暗 —— 它们至少比对角大 1，看了也白看。
值得盯住的帧有两处：
i=2, j=2（
o 对
o）—— 免费收尾，
dp[2][2] 直接抄
dp[1][1] = 1，这是「相同字符不收钱」的现场；
i=5, j=3（
e 对
s）—— 三个邻居
3+1 / 2+1 / 4+1，最小的是
上方（删除），而这一格恰好就是官方样例能骗过「倒着扫」的原因（见 9.1）。
四、完整推演表
以
horse -> ros 为主例（对应动画的 15 个格子帧 + 5 个边界帧 + 1 个收尾帧，共 22 帧）：
答案是右下角的
3。几个值得单独看的格子：
dp[1][1] = 1：h 对 r 不同，对角 0+1=1、上方 1+1=2、左方 1+1=2 —— 替换最便宜。第一格就说明替换是有用的：只许插删的话这里是 2。dp[2][2] = 1：o 对 o，免费收尾，直接抄 dp[1][1]。dp[3][1] = 2：r 对 r，抄的是 dp[2][0] = 2 —— 边界格参与了正经转移，这就是为什么第一列必须是对的。dp[5][3] = 3：e 对 s 不同，对角 dp[4][2]=3 加 1 得 4、上方 dp[4][3]=2 加 1 得 3、左方 dp[5][2]=4 加 1 得 5 —— 取上方（删掉 e）。
最后这条是本篇的伏笔：
右下角这一格的最小值恰好落在「上方」。第五节会把滚动数组讲清楚，而 9.1 会告诉你：上方恰好是「倒着扫」唯一不会弄错的那一项 —— 官方样例就是这么把一个真 bug 藏起来的。
五、追问：压到 O(n)，只丢一格
看转移式：
dp[i][j] 只依赖
上一行（
dp[i-1][j-1]、
dp[i-1][j]）和
本行左邻（
dp[i][j-1]）。更早的行完全用不到 —— 那整张表就没必要留着。
用一行
buf 滚过去：
buf[j] 在写之前装的是上一行的
dp[i-1][j]（上方），写完变成
dp[i][j]；
buf[j-1] 是刚写完的
dp[i][j-1]（左方）。三个邻居里：
三个方向里只有对角不在数组里，所以只需要一个标量
prev 把它接住：
def minDistance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
a, b = list(word1), list(word2)
buf = list(range(n + 1)) # 第 0 行直接当初值
for i in range(1, m + 1):
prev = buf[0] # dp[i-1][0]：先备份，再覆盖
buf[0] = i
for j in range(1, n + 1):
tmp = buf[j] # dp[i-1][j]：写完就没了，先存下来
if a[i - 1] == b[j - 1]:
buf[j] = prev # 对角，免费收尾
else:
buf[j] = 1 + min(prev, buf[j], buf[j - 1])
prev = tmp # 下一格的对角
return buf[n]
两个「先存再写」的位置别写反：
prev = buf[0] 必须在
buf[0] = i 之前，
tmp = buf[j] 必须在写
buf[j] 之前 —— 每行开头和每格开头各有一次覆盖，
覆盖之前的那一刻是拿到旧值的唯一机会。
还想再抠一点：让短的串当列，空间就是
O(min(m, n))。答案对两个串是对称的（编辑距离
dist(a,b) = dist(b,a)），所以随便交换。
第二个动画就是这次压缩本身：背景是
同一张表（整张淡化），上一行被一格一格擦掉、本行被一格一格点亮，下面那条
buf 就是活着的那部分；金色虚线的格子是被覆盖掉的对角，右侧
prev 芯片里装的就是它的遗言。跑到最后
buf 只剩一行，答案照旧是
buf[n] = 3。
六、Java 版
public int minDistance(String word1, String word2) {
char[] a = word1.toCharArray();
char[] b = word2.toCharArray();
int m = a.length, n = b.length;
int[] buf = new int[n + 1];
for (int j = 0; j <= n; j++) buf[j] = j; // 第 0 行
for (int i = 1; i <= m; i++) {
int prev = buf[0]; // dp[i-1][0]，先备份再覆盖
buf[0] = i;
for (int j = 1; j <= n; j++) {
int tmp = buf[j]; // dp[i-1][j]
if (a[i - 1] == b[j - 1]) {
buf[j] = prev; // 相同：免费收尾
} else {
buf[j] = 1 + Math.min(prev, Math.min(buf[j], buf[j - 1]));
}
prev = tmp;
}
}
return buf[n];
}
面试时建议
先写二维版、再当场改成一维：二维版就是去掉
buf/prev 这层舞蹈、改成
int[][] dp，两份代码的转移完全一样。直接甩一维版反而容易让面试官怀疑你没想清楚对角线为什么能丢。
七、边界情况
- 任一串为空：
word1 = "" 答案是 len(word2)，反之亦然。上面的一维代码天然处理：n = 0 时内层循环不跑，return buf[0] = m。
- 两串相等：答案 0，且每个格子都走「免费收尾」分支 —— 这是检验
match 分支的最短用例。
- 单字符：
a -> b 是 1（替换）、aa -> a 是 1（删除）、a -> aa 是 1（插入）。
horse -> ros 与 ros -> horse：答案都是 3 —— 编辑距离是对称的，这也是「短的当列」这步优化的合法性来源。- 含 emoji 等非 BMP 字符：Python 用
list(word) 按码点拆；JavaScript 用 Array.from。.length / s[i] 按 UTF-16 码元切，会把一个 emoji 数成 2 个字符（LC 5 里踩过同一个坑）。Java 的 toCharArray 同样是码元，涉及增补字符时要先转码点数组。
八、复杂度
要
输出具体操作序列（而不仅是最少步数）时，滚动数组不够用 —— 回溯需要整张表。要么退回
O(m·n) 空间存
parent，要么用 Hirschberg 分治把空间压回线性、时间翻倍。面试里能主动提到「值和方案是两个存储需求」是加分的。
九、常见坑
9.1 内层倒着扫（官方样例恰好看不出来）
0/1 背包的肌肉记忆是「内层倒着扫，防止重复选取」。编辑距离
必须顺着扫：
buf[j-1] 要的是本行刚写的值，倒着扫拿到的还是上一行的。
更阴的是这个 bug
在官方样例上是过的 ——
horse -> ros 照样输出 3。原因可以算出来：倒着扫时，三个邻居里只有「上方」没被弄错（
buf[j] 写之前本来就是上一行的值），而
dp[5][3] 的三个候选是
对角 3+1 / 上方 2+1 / 左方 4+1，最小值
恰好落在上方。侥幸。
反例随手一抓就是：
abc -> abc 这个反例只有 3 个字符 —— 拿它当单测，倒扫的代码第一行就现原形。
9.2 相同字符也收 1
把
if 分支漏了、统一写
1 + min(...)：
horse -> ros 会输出 5。相等的那一对必须免费，否则「两串相等」这种最简单的情况都得不到 0。
9.3 第一行 / 第一列填 0
边界是语义（空串变
j 个字符要插
j 次），不是没算的占位符。全填 0 的代码在
horse -> ros 上输出 2，在
"" -> "a" 上输出 0 —— 后者连人眼都能看出错。
9.4 少了「替换」这一项
只留
dp[i-1][j] 和
dp[i][j-1] 两个邻居，写出来的其实是「只允许插入和删除」的题（LC 583）——
horse -> ros 得 4 而不是 3。反过来记：
LC 583 就该删掉替换那一项，它的答案是
m + n - 2 * LCS。
9.5 prev 的更新时机
tmp = buf[j] 必须在写
buf[j] 之前，
prev = tmp 在格子收尾时做。写成
prev = buf[j]（写在最后）会把本行刚算出来的新值当成下一格的对角 ——
horse -> ros 输出 4。每行开头那次同理：先
prev = buf[0] 再
buf[0] = i。
9.6 只留一行还想去重建操作序列
滚动数组回答的是「最少几步」，不回答「怎么走」。要序列就老老实实存整张表（或上 Hirschberg 分治）。面试追问「把操作打出来」时，答「一维版只为步数，方案需要另存
parent」比硬编强得多。
十、面试怎么答
- 先立两个锚："
dp[i][j] 是 a 的前 i 个字符变成 b 的前 j 个字符的最少操作数 —— 双串型必须用前缀对前缀，因为操作会在任意位置增删。"
- 把三种操作对到三个邻居：替换对角、删除上方、插入左方；字符相同时免费收尾。这一步说清楚，代码就是听写。
- 主动说对称性："插入和删除的标注互换不影响数值，但会影响操作序列的重建。" —— 这句话能直接把你和背题的人分开。
- 再答空间压缩："三个邻居里只有对角会被覆盖，所以一个
prev 就够；每行开头 buf[0] 也要先备份。空间 O(min(m, n))。"
- 主动给反例："内层不能倒着扫 —— 官方样例测不出来，
abc -> abc 一测就挂。" 顺带点破为什么官方样例失效（最小值恰好落在唯一没错位的上方）。
- 报变体：只许删除是 LC 583（
m + n - 2*LCS）；求最长公共子序列是 LC 1143（同一张表的另一种记账）；要输出方案回二维表取 parent，空间敏感就 Hirschberg 分治。
结语
编辑距离是「双串型 DP」的定型题：
第一问考你敢不敢一次下两个锚 —— 前缀对前缀，转移自己长出来；第二问考你知不知道三个依赖方向里哪一个是易碎的 —— 对角线被滚动数组覆盖，所以值得一个专门的标量去接。 上一篇 LC 300 的锚是「以 i 结尾」，这一篇的锚是「前 i 个字符」，两次的破局动作都是先把状态钉死、再谈优化。而真正的坑从不在转移式里，在推进顺序里 —— 官方样例恰好让最小值落在唯一没被破坏的那一项上，
abc -> abc 才是这道题真正的试金石。