LeetCode 72. Edit Distance（编辑距离）动态规划详解
编辑距离是经典字符串动态规划问题，也是很多高级题目的基础。题目如下。leetcode
给定两个字符串 word1 和 word2，返回将 word1 转换为 word2 所需的最少操作数。允许的操作有三种：
- 插入一个字符
- 删除一个字符
- 替换一个字符
leetcode
示例：leetcode
- word1 = “horse”, word2 = “ros”，输出 3
- word1 = “intention”, word2 = “execution”，输出 5
字符串长度范围是 0 ~ 500，只包含小写字母。leetcode
一、核心思路：用前缀定义状态
整个问题的关键在于：不要直接从整串去想，而是用「前缀」来描述状态。
定义状态：
dp[i][j]表示：把 word1 的前 i 个字符（下标 0…i-1）转换成 word2 的前 j 个字符（下标 0…j-1）所需的最少操作数。leetcode+1
这样，最终答案就是：
dp[m][n]，其中 m = len(word1)， n = len(word2)。leetcode+1
**直观理解：**dp 是一个二维表，行是 word1 前缀长度 0…m，列是 word2 前缀长度 0…n，每个格子是「把某个前缀变成另一个前缀的最小编辑次数」。leetcode+1
二、边界初始化：只有插入或只有删除
当某一边是空串时，只剩下「全插入」或者「全删除」两种情况。leetcode+1
dp[0][0] = 0
空串变空串，不需要任何操作。leetcode
dp[i][0] = i（i >= 1）
把 word1 的前 i 个字符变成空串，只能删掉这 i 个字符，所以是 i。leetcode
dp[0][j] = j（j >= 1）
把空串变成 word2 的前 j 个字符，只能插入 j 个字符，所以是 j。leetcode
这部分在代码里就是第一行和第一列的初始化。leetcode
三、状态转移：三种操作对应的来源状态
现在考虑一般情况：i >= 1 且 j >= 1。当前需要处理的是两个前缀的最后一个字符：
word1[i-1]和word2[j-1]。leetcode+1
分两种情况：
1. 字符相等：不需要额外操作
如果word1[i-1] == word2[j-1]，说明这两个前缀的最后一个字符已经相同了，不需要再对它们做操作：leetcode+1
直接继承前一个状态：
dp[i][j] = dp[i-1][j-1]也就是「把前 i-1 个变成前 j-1 个」的代价，完全沿用到前 i 和前 j。leetcode+1
2. 字符不等：删除 / 插入 / 替换
如果word1[i-1] != word2[j-1]，需要做一次操作，使得「最后一个字符」能够对齐。这里的难点在于，把「操作」和「来源状态」一一对应地理解清楚。leetcode+1
2.1 删除：来自dp[i-1][j] + 1
**动作：**删除 word1 的最后一个字符word1[i-1]。
删除后，word1 的前缀长度从 i 变成 i-1，而 word2 仍然是前 j 个字符。
于是问题变成：「把 word1 的前 i-1 个字符变成 word2 的前 j 个字符」，这就是dp[i-1][j]。
再加上这一次删除操作，所以：
dp[i][j] = dp[i-1][j] + 1注意思考顺序是：先解决更小的子问题dp[i-1][j]，再通过一次“删除最后一个字符”的操作扩展到dp[i][j]。leetcode+1
2.2 插入：来自dp[i][j-1] + 1
插入比较容易混淆，虽然是往 word1 里插入，但来源状态是dp[i][j-1]。
**目标：**让 word1 的前 i 个字符最终变成 word2 的前 j 个字符，并且末尾应为word2[j-1]。
假设此时已经处理好了dp[i][j-1]，即「把 word1 的前 i 个字符变成 word2 的前 j-1 个字符」。
接下来只需要在 word1 的末尾插入word2[j-1]这个字符，就能匹配上「前 j 个字符」。
所以来源是：
dp[i][j] = dp[i][j-1] + 1这里的直觉是：先对齐 word2 的前 j-1 个字符，再插入最后一个，使目标从长度 j-1 扩展到 j。leetcode+1
2.3 替换：来自dp[i-1][j-1] + 1
**动作：**把word1[i-1]替换成word2[j-1]。
替换之前，前面已经有 i-1 和 j-1 个字符，问题是「如何把 word1 的前 i-1 个变成 word2 的前 j-1 个」，即dp[i-1][j-1]。
替换本身只处理最后一个字符，让它们变得相同。
因此：
dp[i][j] = dp[i-1][j-1] + 1思路同样是：先搞定更短的前缀 (i-1, j-1)，然后通过一次替换把长度扩展到 (i, j)。leetcode+1
3. 综合不等时的转移方程
当word1[i-1] != word2[j-1]时，需要在三种方案里取最小值：leetcode+1
dp[i][j] = min( dp[i-1][j] + 1, // 删除 dp[i][j-1] + 1, // 插入 dp[i-1][j-1] + 1 // 替换 )配合字符相等时的情况，可以总结成：
如果
word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]否则：
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)
这就是经典编辑距离 DP 的完整转移。leetcode+1
四、用一个小例子感受表格
比如 word1 = “ab”，word2 = “abc”：
- 行下标 i = 0…2，列下标 j = 0…3。
dp[0][j] = j，dp[i][0] = i，先把第一行第一列填出来。- 然后按顺序填 (1,1)、(1,2)、(1,3)、(2,1)…，每一格都只依赖「上方、左方、左上方」。
- 在纸上画出 3×4 的网格，用上面三种操作去解释每个格子，可以很快把 i / j 和 i-1 / j-1 的关系彻底吃透。
五、C 语言实现代码（含内存释放）
下面是一个用二维数组实现的 C 解法，对应上面所有的状态定义与转移：leetcode
#include<stdio.h>#include<stdlib.h>#include<string.h>#defineINT_MAX0x7fffffff#defineMIN(a,b)((a)<(b)?(a):(b))intminDistance(char*word1,char*word2){intword1_len,word2_len,i,j,result;intinsert,delete,replace;int**dp;if(word1==NULL||word2==NULL)return0;word1_len=strlen(word1);word2_len=strlen(word2);dp=(int**)malloc((word1_len+1)*sizeof(int*));for(i=0;i<=word1_len;i++){dp[i]=(int*)malloc((word2_len+1)*sizeof(int));for(j=0;j<=word2_len;j++)dp[i][j]=INT_MAX;}dp[0][0]=0;for(i=1;i<=word1_len;i++)dp[i][0]=i;for(j=1;j<=word2_len;j++)dp[0][j]=j;for(i=1;i<=word1_len;i++){for(j=1;j<=word2_len;j++){if(word1[i-1]==word2[j-1]){dp[i][j]=dp[i-1][j-1];}else{delete=dp[i-1][j]+1;insert=dp[i][j-1]+1;replace=dp[i-1][j-1]+1;dp[i][j]=MIN(delete,MIN(insert,replace));}}}result=dp[word1_len][word2_len];for(i=0;i<=word1_len;i++)free(dp[i]);free(dp);dp=NULL;returnresult;}二维 dp 使用 malloc 动态分配，并在最后完整 free，避免内存泄漏。leetcode
时间复杂度 O(mn)，空间复杂度 O(mn)，对于 0 ~ 500 的长度完全可以接受。leetcode+1
六、常见疑问：为什么会出现 i / i-1、j / j-1 混在一起？
原因在于：
dp[i][j]的 i、j 是「前缀长度」。- 字符访问使用的是数组下标，从 0 开始，所以最后一个字符是
word1[i-1]、word2[j-1]。 - 转移时，总是从「更短的前缀」(i-1, j)、(i, j-1)、(i-1, j-1) 出发，加 1 次操作，推到「更长的前缀」(i, j)。leetcode+1
一旦把「dp 里的 i/j = 前缀长度」和「字符串下标 = i-1/j-1」区分开，就不会再被这些下标搞乱。
你可以直接把这篇博客贴到 CSDN，然后根据自己的理解再加上图（例如 DP 表格截图）或者手写示意图，会更容易被读者看懂。
参考链接
- LeetCode 72. Edit Distance
- LeetCode 72. Edit Distance - 提交记录
