动态规划核心思路dp 定义和 LCS 完全一样dp[i][j]把 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作次数。边界条件空串情况如果word1是空串i0转换成word2前 j 个字符需要插入 j 次→dp[0][j] j如果word2是空串j0转换成空串需要删除 i 次→dp[i][0] i状态转移方程核心分两种情况情况 1c1 c2最后一个字符相同这两个字符已经匹配了不需要任何操作直接继承前面的结果plaintextdp[i][j] dp[i-1][j-1]比如word1abcword2adc最后一个字符都是 c那么只需要把 ab 转换成 ad 就行。情况 2c1 ! c2最后一个字符不同有三种操作可以选选操作次数最少的那个再加 1当前这次操作删除 word1 的最后一个字符把word1前 i-1 个转换成word2前 j 个再删最后一个 →dp[i-1][j] 1插入一个字符到 word1 末尾插入的字符正好是c2所以只需要把word1前 i 个转换成word2前 j-1 个 →dp[i][j-1] 1替换 word1 的最后一个字符把c1换成c2然后把word1前 i-1 个转换成word2前 j-1 个 →dp[i-1][j-1] 1所以plaintextdp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1四、完整解题步骤处理边界情况如果其中一个字符串为空直接返回另一个字符串的长度初始化 dp 数组大小为(n1) × (m1)n 是 word1 长度m 是 word2 长度第一行dp[0][j] j第一列dp[i][0] i遍历计算 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返回结果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数组n1行 m1列 vectorvectorint dp(n1,vectorint(m1)); //dp[i][j] 表示word1的前i个和word2前j个 需要将word1转换为word2 //初始化第一列d[i][0] 这种情况就是删除i 所以就是i次 for(int i 0;in;i){ dp[i][0] i; } //初始化第一行 for(int j 0;jm;j){ dp[0][j] j; } //遍历计算dp数组 for(int i 1;in;i){ for(int j 1;jm;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]; } };