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

LeetCode 72. 编辑距离：动态规划经典题解

news 2026/5/4 19:45:51

刷LeetCode中等题时，编辑距离绝对是动态规划的经典代表作——它看似复杂，三种操作（插入、删除、替换）让人无从下手，但只要理清状态定义和转移逻辑，就能轻松破解。今天就带大家一步步拆解这道题，从题意分析到代码实现，把每一个细节讲透。

一、题目解读：到底要解决什么问题？

题目很简洁：给定两个单词word1和word2，返回将word1转换成word2所使用的最少操作数。

允许的三种操作（对一个单词进行）：

插入一个字符：比如word1是“abc”，word2是“abdc”，可以在word1的b和c之间插入d，完成转换。
删除一个字符：比如word1是“abcd”，word2是“abc”，删除word1的d即可。
替换一个字符：比如word1是“abc”，word2是“adc”，将word1的b替换成d即可。

核心难点：三种操作可以任意组合，如何找到“最少步骤”？—— 动态规划的核心就是“最优子结构”，把大问题拆成小问题，逐个解决。

二、动态规划思路拆解（核心部分）

动态规划解题，关键就3步：定义dp数组、确定边界条件、推导状态转移方程。我们一步步来：

1. 定义dp数组

设word1的长度为n，word2的长度为m，定义dp[i][j]：将word1前i个字符（word1[0…i-1]）转换成word2前j个字符（word2[0…j-1]）所需的最少操作数。

为什么是i-1和j-1？因为dp数组的下标从0开始，而字符串的下标也从0开始，dp[0][0]表示两个空串的转换，dp[1][1]才对应两个单词的第一个字符，这样定义更直观，避免下标混乱。

2. 确定边界条件

边界情况就是“其中一个单词为空串”的场景：

如果word1为空（i=0），那么要转换成word2前j个字符，只能不断插入j个字符，所以dp[0][j] = j。
如果word2为空（j=0），那么要转换成空串，只能不断删除word1前i个字符，所以dp[i][0] = i。

比如dp[0][3] = 3（空串转成3个字符，插入3次），dp[2][0] = 2（2个字符转成空串，删除2次）。

3. 推导状态转移方程

这是最关键的一步，我们分两种情况讨论：word1的第i个字符（word1[i-1]）和word2的第j个字符（word2[j-1]）是否相等。

情况1：word1[i-1] == word2[j-1]

此时，两个字符已经匹配，不需要做任何操作，最少操作数就等于“word1前i-1个字符转word2前j-1个字符”的操作数，即：

dp[i][j] = dp[i-1][j-1]

比如word1是“abc”，word2是“adc”，当i=3、j=3时，word1[2] = c，word2[2] = c，此时dp[3][3] = dp[2][2]。

情况2：word1[i-1] != word2[j-1]

此时需要进行插入、删除、替换三种操作中的一种，取这三种操作的最少步骤即可，对应三个方向的状态：

删除操作：删除word1的第i个字符，此时dp[i][j] = dp[i-1][j] + 1（删除1次，加上之前的操作数）。
插入操作：在word1的第i个字符后插入一个和word2[j-1]相同的字符，此时dp[i][j] = dp[i][j-1] + 1（插入1次，加上之前的操作数）。
替换操作：将word1的第i个字符替换成word2[j-1]，此时dp[i][j] = dp[i-1][j-1] + 1（替换1次，加上之前的操作数）。

所以，状态转移方程为：

dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)

三、完整代码实现（TypeScript）

结合上面的思路，直接上代码，每一行都加了详细注释，对应我们拆解的逻辑：

functionminDistance(word1:string,word2:string):number{letn=word1.length;// word1的长度letm=word2.length;// word2的长度// 边界情况：有一个字符串为空串，操作数就是另一个字符串的长度if(n*m==0){returnn+m;}// 初始化dp数组：n+1行（word1的0~n个字符），m+1列（word2的0~m个字符）constdp:number[][]=Array.from({length:n+1},()=>newArray(m+1));// 边界状态初始化：word2为空时，dp[i][0] = i（删除i次）for(leti=0;i<n+1;i++){dp[i][0]=i;}// 边界状态初始化：word1为空时，dp[0][j] = j（插入j次）for(letj=0;j<m+1;j++){dp[0][j]=j;}// 填充dp数组：遍历所有i和j，计算每个dp[i][j]的值for(leti=1;i<n+1;i++){for(letj=1;j<m+1;j++){// 左：删除操作，dp[i-1][j] + 1letleft=dp[i-1][j]+1;// 下：插入操作，dp[i][j-1] + 1letdown=dp[i][j-1]+1;// 左下：替换/不操作，先取dp[i-1][j-1]letleft_down=dp[i-1][j-1];// 字符不相等时，替换操作需要+1if(word1.charAt(i-1)!=word2.charAt(j-1)){left_down+=1;}// 取三种操作的最小值，赋值给dp[i][j]dp[i][j]=Math.min(left,Math.min(down,left_down));}}// dp[n][m]就是word1完整转word2的最少操作数returndp[n][m];};