Edit Distance 是 LeetCode Hot 100 里面一道非常经典的字符串动态规划题。
这道题在动态规划专题里非常有代表性，因为它不仅考察最基础的状态定义和状态转移，还会让人真正理解：
两个字符串之间的“最优操作过程”，是如何被动态规划一步步拆出来的。
题目看起来像是在做字符串编辑： 给你两个单词，允许你进行插入、删除、替换三种操作，问最少多少步可以把 word1 变成 word2。
但真正做题时你会发现，这并不是简单地“模拟操作”，而是一个非常标准的二维动态规划问题。
你给出的这份 Java 代码，就是这道题最经典、最标准的一种写法：
二维 DP
它的核心思想是：
-
用
f[i][j] -
然后根据最后一个字符的关系，去考虑插入、删除、替换三种选择
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定两个字符串 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
你可以进行的操作有三种：
-
插入一个字符
-
删除一个字符
-
替换一个字符
例如：
word1 = "horse"
word2 = "ros"
一个可行的转换过程是：
horse -> rorse （将 h 替换成 r）
rorse -> rose （删除一个 r）
rose -> ros （删除一个 e）
总共需要 3 步，所以答案是：
3
这道题要求的是 最少操作次数，不是随便给出一个转换过程。
示例
示例 1
输入：word1 = "horse", word2 = "ros"
输出：3
解释如上，总共 3 次操作。
示例 2
输入：word1 = "intention", word2 = "execution"
输出：5
这是这道题另一个非常经典的例子，最少需要 5 步。
最直接的想法是什么？
如果最开始不去想动态规划，很多人会下意识地想：
-
从
word1开始，一步步尝试插入、删除、替换 -
看看怎么改成
word2 -
在所有操作路径里找最短的一条
但这个思路一旦真的写下去，会发现复杂度非常高。 因为每一步都可能分叉出多种操作方式，而且很多中间状态会被重复计算。
例如某个前缀变成另一个前缀的最少步数，可能会在不同递归分支中反复出现。 这正是动态规划最适合出场的信号：
-
存在重复子问题
-
存在最优子结构
所以这道题最核心的突破口，就是把“大字符串转换问题”拆成“前缀之间的转换问题”。
核心思路：定义状态
这道题最关键的一步，就是定义状态。
我们定义：
f[i][j] = 将 word1 的前 i 个字符转换成 word2 的前 j 个字符的最少操作数
注意这里说的是：
-
word1的前i个字符 -
word2的前j个字符
例如：
-
f[0][0]表示空串变空串，需要 0 步 -
f[3][2]表示把word1前 3 个字符变成word2前 2 个字符的最少操作数
一旦状态定义清楚，整道题就会变得非常规范。
状态转移怎么推？
假设我们现在要求：
f[i][j]
也就是把 word1[0..i-1] 转换成 word2[0..j-1] 的最少操作数。
我们重点看最后一个字符：
-
word1.charAt(i - 1) -
word2.charAt(j - 1)
这时候有三种典型操作：
1. 插入
如果最后一步是“插入一个字符”，那意味着我们先把：
word1 前 i 个字符 -> word2 前 j-1 个字符
做好，然后再插入 word2 的最后一个字符。
所以代价是：
f[i][j-1] + 1
2. 删除
如果最后一步是“删除一个字符”，那意味着我们先把：
word1 前 i-1 个字符 -> word2 前 j 个字符
做好，然后删除 word1 的最后一个字符。
所以代价是：
f[i-1][j] + 1
3. 替换 / 不操作
如果最后一步考虑的是两个字符串最后一个字符对应：
-
如果这两个字符相同，就不需要额外操作
-
如果不同，就需要替换一次
所以代价是：
f[i-1][j-1] + cost
其中：
cost = 0 当最后字符相同
cost = 1 当最后字符不同
所以最终状态转移方程就是：
f[i][j] = min(
f[i][j-1] + 1,
f[i-1][j] + 1,
f[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1)
)
这正是你代码里的核心公式。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length(), m = word2.length();
int[][] f = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// word1 为空串，只能不断插入
if (i == 0) {
f[i][j] = j;
continue;
}
// word2 为空串，只能不断删除
if (j == 0) {
f[i][j] = i;
continue;
}
f[i][j] = Math.min(
f[i][j - 1] + 1,
Math.min(
f[i - 1][j] + 1,
f[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1)
)
);
}
}
return f[n][m];
}
}
代码拆解
这段代码是编辑距离问题最标准的二维 DP 模板。 如果你能真正理解它，后面很多字符串 DP 题会顺很多。
1. 为什么 f 要开成 (n+1) x (m+1)？
int[][] f = new int[n + 1][m + 1];
因为状态 f[i][j] 表示的是“前 i 个字符”和“前 j 个字符”。
这里的 i 和 j 都有可能等于 0，表示空前缀。
例如：
-
f[0][0]：空串变空串 -
f[0][j]：空串变成word2前j个字符 -
f[i][0]：word1前i个字符变成空串
所以数组必须多开一行一列，用来表示“空串”这一类状态。
这是字符串 DP 题里非常常见的做法。
2. 为什么当 i == 0 时，f[i][j] = j？
if (i == 0) {
f[i][j] = j;
continue;
}
因为这表示：
空串 -> word2 的前 j 个字符
如果从空串变成一个长度为 j 的字符串，那唯一能做的就是不断插入字符。
插入 j 个字符，总代价就是：
j
例如：
-
"" -> "a"：1 步 -
"" -> "abc"：3 步
所以：
f[0][j] = j
3. 为什么当 j == 0 时，f[i][j] = i？
if (j == 0) {
f[i][j] = i;
continue;
}
这表示：
word1 的前 i 个字符 -> 空串
如果把一个长度为 i 的字符串变成空串，那只能不断删除字符。
删除 i 次，总代价就是：
i
例如：
-
"a" -> ""：1 步 -
"abc" -> ""：3 步
所以：
f[i][0] = i
4. 为什么普通位置要取三者最小？
f[i][j] = Math.min(
f[i][j - 1] + 1,
Math.min(
f[i - 1][j] + 1,
f[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1)
)
);
因为当前位置对应的前缀转换，最后一步只可能属于三种情况：
插入
f[i][j-1] + 1
删除
f[i-1][j] + 1
替换 / 不操作
f[i-1][j-1] + cost
编辑距离问的是“最少操作次数”，所以当然要从这三种可能里取最小值。
这一步就是整个 DP 的核心。
5. 为什么字符比较是 word1.charAt(i - 1) 和 word2.charAt(j - 1)？
因为：
f[i][j]
表示的是“前 i 个字符”和“前 j 个字符”。
那么这两个前缀的最后一个字符，下标自然分别是：
-
i - 1 -
j - 1
这是很多字符串 DP 题中最容易混淆的地方。 一定要注意：状态是“长度”，字符访问是“下标”，所以要减一。
手动模拟一遍
我们用一个简单例子来走一下：
word1 = "horse"
word2 = "ros"
为了简化说明，我们先只看前几个字符。
设：
-
行表示
word1的前缀 -
列表示
word2的前缀
初始边界：
"" r o s
"" 0 1 2 3
h 1
o 2
r 3
s 4
e 5
计算 f[1][1]："h" -> "r"
最后字符不同，所以考虑三种操作：
-
插入：
f[1][0] + 1 = 2 -
删除：
f[0][1] + 1 = 2 -
替换：
f[0][0] + 1 = 1
所以：
f[1][1] = 1
计算 f[2][2]："ho" -> "ro"
最后字符 o 和 o 相同，所以替换代价为 0：
-
插入：
f[2][1] + 1 -
删除：
f[1][2] + 1 -
对齐：
f[1][1] + 0
因为最后字符相同，通常第三项会更优。
一路推下去，最终：
f[5][3] = 3
也就是答案。
为什么这个方法是正确的？
因为对于任意两个前缀：
word1 前 i 个字符
word2 前 j 个字符
它们的最优编辑过程，最后一步一定属于下面三种之一：
-
插入
-
删除
-
替换 / 不操作
而在最后一步之前，问题规模都会缩小成一个更短前缀之间的编辑距离问题：
-
插入对应
f[i][j-1] -
删除对应
f[i-1][j] -
替换 / 不操作对应
f[i-1][j-1]
这说明当前最优解可以由更小子问题的最优解推出来，满足动态规划的最优子结构。
因此，这个状态转移是完全正确的。
复杂度分析
时间复杂度
我们需要填满整个二维数组 f，大小为：
(n + 1) * (m + 1)
所以时间复杂度是：
O(n * m)
空间复杂度
二维数组 f 的大小同样是：
O(n * m)
所以空间复杂度也是：
O(n * m)
如果进一步优化，还可以压缩到一维 DP，但二维写法是最经典、最清晰的基础版本。
这道题真正想考什么？
这道题表面上是在做字符串编辑，但本质上考察的是字符串 DP 的基本功。
第一，是否能正确定义“前缀状态”
字符串 DP 里非常常见的套路就是：
先把问题变成前缀和前缀之间的关系。
如果状态定义不清楚，后面的转移就很容易乱。
第二，是否能从“最后一步操作”反推状态转移
编辑距离之所以经典，就是因为它非常适合用“最后一步是什么操作”来拆解问题。
很多动态规划题的关键都在于这一点：
-
不要直接想完整过程
-
要想最后一步怎么来的
第三，是否能处理好边界条件
这题里最容易出错的地方往往不是公式本身，而是：
-
空串怎么处理
-
下标和长度怎么对应
-
i - 1、j - 1会不会越界
所以这道题特别能检验代码细节是否扎实。
和最长公共子序列有什么区别？
这两题都属于字符串 DP，形式上有点像，但本质目标不同。
编辑距离
求的是：
把一个字符串变成另一个字符串的最少操作数
允许插入、删除、替换。
最长公共子序列
求的是：
两个字符串的最长公共子序列长度
重点是匹配，不是编辑。
所以虽然它们都用二维 DP，但状态含义和转移逻辑完全不同。
编辑距离更像是“操作成本型 DP”。
总结
这道题的核心思想可以概括成一句话：
用 f[i][j] 表示两个字符串前缀之间的最小编辑距离，再根据插入、删除、替换三种操作进行状态转移。
具体步骤就是：
-
定义状态：
f[i][j] = word1 前 i 个字符转换成 word2 前 j 个字符的最少操作数
-
初始化边界：
f[0][j] = j
f[i][0] = i
-
对于普通位置，取三种操作中的最小值：
插入：f[i][j-1] + 1
删除：f[i-1][j] + 1
替换/不操作：f[i-1][j-1] + cost
-
最终答案就是：
f[n][m]
这样就能在：
O(n * m)
的时间复杂度和：
O(n * m)
的空间复杂度下解决问题。
这是一道非常经典、也非常值得反复理解的字符串动态规划题。 因为它会让你真正体会到：
-
前缀状态的定义方式
-
最后一步分析法如何用于字符串问题
-
二维 DP 表到底在记录什么
-
为什么边界初始化在字符串 DP 中如此重要
把这道题真正吃透之后，再去看：
-
不同的子序列
-
最长公共子序列
-
删除操作
-
正则表达式匹配
这些字符串 DP 题时，你会明显更容易抓住套路。
