LeetCode 72困难二维 DP
编辑距离 图解题解
这道题到底在问什么
把 word1 变成 word2，允许插入、删除、替换，求最少操作数。
- word1
- "horse"
- word2
- "ros"
- 输出
- 3
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合二维 DP。
- 4空串到目标只能插入，初始化第一行第一行 dp[0][j]=j：空串变 word2 前 j 个字符，只能逐个插入，所以是 0,1,2,3。
- 5源串到空串只能删除，初始化第一列第一列 dp[i][0]=i：word1 前 i 个字符变空串，只能逐个删除，所以是 0,1,2,3,4,5。
- 6字符相同，不增加操作，继承左上word1[1]='o' == word2[1]='o'：这一格不花操作，直接继承左上 dp[1][1]=1 → dp[2][2]=1。
- 7字符不同，考虑插入、删除、替换word1[0]='h' ≠ word2[0]='r'：要从三个邻居转移——上=删除 dp[0][1]，左=插入 dp[1][0]，左上=替换 dp[0][0]。
- 8三种操作取最小再 +1r ≠ s：dp[3][3]=min(上 2, 左 2, 左上 1)+1=2 —— 选最省的左上(替换)再加一步。
- 9逐格填表，依赖左、上、左上每一格只看左、上、左上三个邻居，按字符相同/不同套用规则，从左上往右下逐格推。
- 10horse 到 ros 最少 3 步右下角 dp[5][3]=min(上 2, 左 4, 左上 3)+1=3，就是 horse→ros 的最少操作数。
- 11返回右下角 dp[m][n]答案永远在右下角 dp[m][n]=dp[5][3]=3：word1 整体变成 word2 的最少编辑步数。
- 14把这句话记住，下次遇到同类题，就能更快选出方向。
- 19把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：字符不同时只考虑替换
✓ 对：插入、删除、替换都要比较
最优路径不一定用替换
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
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]C++
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
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];
}
};Java
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
return dp[m][n];
}
}套路模板 · 编辑距离二维 DP
# 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]复杂度
时间复杂度
O(mn)
m×n 个状态，每格 O(1) 转移（取三者最小）
空间复杂度
O(mn)
二维 dp 表 m×n；每格只依赖上一行，可滚动到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 编辑距离 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
三种操作分别对应哪个转移？+
插入=dp[i][j-1]+1、删除=dp[i-1][j]+1、替换=dp[i-1][j-1]+1；末字符相同时替换项不 +1。
为什么是二维 DP？+
状态依赖两串各自前缀位置 i、j，二维表自然刻画；可滚动到一维 O(n)。
复杂度？+
O(m·n) 时间、O(min(m,n)) 空间(滚动)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。