题目描述
思路解析动画文字版
关键不是背模板，而是看懂为什么这题适合二维 DP。
1. 初始化第一行：空串→word2 只能插入：第一行 dp[0][j]=j：空串变 word2 前 j 个字符，只能逐个插入，所以是 0,1,2,3。
2. 初始化第一列：word1→空串只能删除：第一列 dp[i][0]=i：word1 前 i 个字符变空串，只能逐个删除，所以是 0,1,2,3,4,5。
3. 字符相同：免操作，继承左上：word1[1]='o' == word2[1]='o'：这一格不花操作，直接继承左上 dp[1][1]=1 → dp[2][2]=1。
4. 字符不同：看上/左/左上三个方向：word1[0]='h' ≠ word2[0]='r'：要从三个邻居转移——上=删除 dp[0][1]，左=插入 dp[1][0]，左上=替换 dp[0][0]。
5. 三种操作取最小再 +1：r ≠ s：dp[3][3]=min(上 2, 左 2, 左上 1)+1=2 —— 选最省的左上(替换)再加一步。
6. 逐格填表，只依赖左、上、左上：每一格只看左、上、左上三个邻居，按字符相同/不同套用规则，从左上往右下逐格推。
7. horse → ros 最少 3 步：右下角 dp[5][3]=min(上 2, 左 4, 左上 3)+1=3，就是 horse→ros 的最少操作数。
8. 答案在右下角 dp[m][n]：答案永远在右下角 dp[m][n]=dp[5][3]=3：word1 整体变成 word2 的最少编辑步数。
把这句话记住，下次遇到同类题，就能更快选出方向。
迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
边界三连：边界三连：极端输入先过一遍。
几个高频追问，记住答法。
参考代码
class Solution: def minDistance(self, word1, word2): 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], dp[i][j-1], dp[i-1][j-1]) + 1 return dp[m][n]复杂度
- 时间复杂度：O(mn)，m×n 个状态，每格 O(1) 转移（取三者最小）
- 空间复杂度：O(mn)，二维 dp 表 m×n；每格只依赖上一行，可滚动到 O(n)
可套用的代码模板
记牢这张表：状态=两段前缀的编辑距离；相同免费继承左上，不同则「删/插/替」三选一 +1；答案右下角。
Python
# dp[i][j] = word1 前 i 个字符 变 word2 前 j 个字符 的最少操作数dp = [[0]*(n+1) for _ in range(m+1)]for i in range(m+1): dp[i][0] = i # 删 i 次for j in range(n+1): dp[0][j] = 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], # 删 dp[i][j-1], # 插 dp[i-1][j-1]) + 1 # 替return dp[m][n]易错点
面试追问把动画讲成自己的话
追问三种操作分别对应哪个转移？
追问为什么是二维 DP？
追问复杂度？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
戳气球
LeetCode 312 · 困难 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题