编辑距离
Edit Distance
求把 word1 变成 word2 的最少操作数，允许插入、删除、替换一个字符。
在力扣中练习题目描述
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
解题思路
二维 DP · 三种操作
末尾字符相同时不用操作；不同时在替换、删除、插入里取最小
暴力搜索每一步的三种操作会指数爆炸。把问题截成前缀：dp[i][j] 表示把 word1 的前 i 个字符变成 word2 的前 j 个字符，最少要几步。
比较两个末尾字符：
- 相同：不用操作，
dp[i][j] = dp[i-1][j-1]； - 不同：三种操作分别对应三个相邻格，取最小再加 1。
替换：dp[i-1][j-1] + 1
删除：dp[i-1][j] + 1
插入：dp[i][j-1] + 1
自拟主例 "flaw" → "lawn"，答案 2：先删除 f 得到 law，再插入 n 得到 lawn。第一行/第一列不是全 0：空串变成非空串只能不断插入，所以是 0..n 和 0..m。
'f' ≠ 'l'：替换 0 + 1、删除 1 + 1、插入 1 + 1，取最小 1。
- i
- 1
- j
- 1
dp[i][j]：word1 前 i 个字符变成 word2 前 j 个字符的最少操作数；"flaw" → "lawn"
dp[1][1]=min(dp[0][0] + 1, dp[0][1] + 1, dp[1][0] + 1)min(0 + 1, 1 + 1, 1 + 1)=1选中 dp[0][0] 替换
dp[i][j]：word1 前 i 个字符变成 word2 前 j 个字符的最少操作数；"flaw" → "lawn"
dp[4][4]=min(dp[3][3] + 1, dp[3][4] + 1, dp[4][3] + 1)min(2 + 1, 3 + 1, 1 + 1)=2选中 dp[4][3] 插入
按行从左到右填表，三个来源都在左上、上、左，计算当前格时都已确定。时间 O(m × n)，空间 O(m × n)。
易错点
- 第一行、第一列初始化为 0：空串变非空串需要插入/删除，初值应为下标本身。
- 字符相同时也加 1：相同时不需要任何操作，直接继承左上。
- 只比较替换和删除，漏掉插入：三个方向对应三种操作，缺一不可。
滚动数组 · 一维 DP
一行只留 n+1 个数，用 prev 记住被覆盖的左上角
时间相同，空间从 O(m × n) 降到 O(n)；代价是左上角会被覆盖，需要用 prev 暂存，时序更容易写错。
转移只需要上一行和本行左边，因此可以压成一行。
但 dp[j] 被覆盖前是上方值，覆盖后是本行值；左上角 dp[i-1][j-1] 会在上一轮被覆盖。所以每列开始前用 prev 保存旧的 dp[j]，处理完再把 prev 交给下一列：
temp = dp[j] // 旧的上方值，下一列的左上角
dp[j] = ... // 用 prev / dp[j] / dp[j-1] 计算
prev = temp
每行开始还要把 dp[0] 更新为 i（第一列）。时间 O(m × n)，空间 O(n)。
- 1dp[j] = j，第一行。
- 2每行 prev = dp[0]，dp[0] = i。
- 3j 从左到右：temp = dp[j]，用 prev/上方/左方计算，再 prev = temp。
- 4返回 dp[n]。
易错点
- 忘记更新 dp[0]：第一列的删除次数还停留在上一行。
- prev 更新时机不对：先覆盖 dp[j] 再取 temp，会丢掉上方值。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
word1 = "flaw", word2 = "lawn"空串变成长度 i 或 j 的串，只能插入或删除，所以第一行、第一列分别是 0..n 和 0..m。
- word1
- flaw
- word2
- lawn
dp[i][j]：word1 前 i 个字符变成 word2 前 j 个字符的最少操作数；"flaw" → "lawn"
dp[0][0]=0查看 C++ 代码
延伸阅读
- 编辑距离是最经典的二维字符串 DP；最长公共子序列可以看作只允许删除的版本。
- 如果操作代价不同（插入、删除、替换各有价格），把 +1 换成对应代价即可，结构不变。