当前位置：首页 > news >正文

LeetCode 72. Edit Distance（编辑距离）动态规划详解

news 2026/3/26 21:49:55

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 表格截图）或者手写示意图，会更容易被读者看懂。