力扣HOT100(55)多维动态规划 - 编辑距离

动态规划核心思路

dp 定义（和 LCS 完全一样）

dp[i][j]：把 word1 的前 i 个字符，转换成 word2 的前 j 个字符，所需的最少操作次数。

边界条件（空串情况）

• 如果word1是空串（i=0）：转换成word2前 j 个字符，需要插入 j 次→dp[0][j] = j
• 如果word2是空串（j=0）：转换成空串，需要删除 i 次→dp[i][0] = i

状态转移方程（核心，分两种情况）

情况 1：c1 == c2（最后一个字符相同）

这两个字符已经匹配了，不需要任何操作，直接继承前面的结果：

plaintext

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

比如：word1="abc"，word2="adc"，最后一个字符都是 c，那么只需要把 "ab" 转换成 "ad" 就行。

情况 2：c1 != c2（最后一个字符不同）

有三种操作可以选，选操作次数最少的那个，再加 1（当前这次操作）：

1. 删除 word1 的最后一个字符：把word1前 i-1 个转换成word2前 j 个，再删最后一个 →dp[i-1][j] + 1
2. 插入一个字符到 word1 末尾：插入的字符正好是c2，所以只需要把word1前 i 个转换成word2前 j-1 个 →dp[i][j-1] + 1
3. 替换 word1 的最后一个字符：把c1换成c2，然后把word1前 i-1 个转换成word2前 j-1 个 →dp[i-1][j-1] + 1

所以：

plaintext

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

四、完整解题步骤

1. 处理边界情况：如果其中一个字符串为空，直接返回另一个字符串的长度
2. 初始化 dp 数组：
   • 大小为(n+1) × (m+1)，n 是 word1 长度，m 是 word2 长度
   • 第一行：dp[0][j] = j
   • 第一列：dp[i][0] = i
3. 遍历计算 dp 数组：
   • 外层循环：i 从 1 到 n
   • 内层循环：j 从 1 到 m
     • 如果word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
     • 否则：dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1
4. 返回结果：dp[n][m]

class Solution { public: int minDistance(string word1, string word2) { int n = word1.size(); int m = word2.size(); //边界情况 有一个是空串 直接返回另一个长度 if(n * m == 0){ return n + m; } //初始化dp数组：n+1行 m+1列 vector<vector<int>> dp(n+1,vector<int>(m+1)); //dp[i][j] 表示word1的前i个和word2前j个 需要将word1转换为word2 //初始化第一列：d[i][0] 这种情况就是删除i 所以就是i次 for(int i = 0;i<=n;i++){ dp[i][0] = i; } //初始化第一行 for(int j = 0;j<=m;j++){ dp[0][j] = j; } //遍历计算dp数组 for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(word1[i-1] == word2[j-1]){//如果第i个和第j个相等说明这个元素不用改，所以改动的次数和前i-1个一样 如下： dp[i][j] = dp[i-1][j-1]; } else{ //如果最后一个不一样 有三种操作：删 添加 替代 //前i-1个和那边的前j个相同 然后删掉word1的最后一个 int del = dp[i-1][j] +1; //前i个和那边的前j-1个相同 然后插入word2的最后一个 int ins = dp[i][j-1] +1; //前i-1和那边的前j-1相同 然后word1的最后一个替换成word2中的最后一个 int rep = dp[i-1][j-1] +1; dp[i][j] = min(del,min(ins,rep)); } } } return dp[n][m]; } };