C++刷LeetCode（72. 编辑距离）【动态规划】

糖逗

题目描述：

1. 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
   
2. 
   
3. 你可以对一个单词进行如下三种操作：
   
4. 
   
5. 插入一个字符
   
6. 删除一个字符
   
7. 替换一个字符
   
8.  
   
9. 
   
10. 示例 1：
    
11. 
    
12. 输入：word1 = "horse", word2 = "ros"
    
13. 输出：3
    
14. 解释：
    
15. horse -> rorse (将 'h' 替换为 'r')
    
16. rorse -> rose (删除 'r')
    
17. rose -> ros (删除 'e')
    
18. 示例 2：
    
19. 
    
20. 输入：word1 = "intention", word2 = "execution"
    
21. 输出：5
    
22. 解释：
    
23. intention -> inention (删除 't')
    
24. inention -> enention (将 'i' 替换为 'e')
    
25. enention -> exention (将 'n' 替换为 'x')
    
26. exention -> exection (将 'n' 替换为 'c')
    
27. exection -> execution (插入 'u')
    
28.  
    
29. 
    
30. 提示：
    
31. 
    
32. 0 <= word1.length, word2.length <= 500
    
33. word1 和 word2 由小写英文字母组成
    
34. 
    
35. 来源：力扣（LeetCode）
    
36. 链接：https://leetcode-cn.com/problems/edit-distance
    
37. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minDistance(string word1, string word2) {
   
4.         int len1 = word1.size(), len2 = word2.size();
   
5.         vector<vector<int> >dp(len1+1, vector<int>(len2+1, 0));
   
6.         //初始化
   
7.         for(int i = 0; i <= len1; i++){
   
8.             dp[i][0] = i;
   
9.         }
   
10.         for(int j = 0; j <= len2; j++){
    
11.             dp[0][j] = j;
    
12.         }
    
13.         //动态规划
    
14.         for(int i = 1; i <= len1; i++){
    
15.             for(int j = 1; j <= len2; j++){
    
16.                 dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
    
17.                 if(word1[i-1] == word2[j-1]){//这里设置dp是(len1+1, len2+1)比word1和word2的长度多1位
    
18.                     dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
    
19.                 }
    
20.             }
    
21.         }
    
22.         return dp[len1][len2];
    
23.     }
    
24. };

复制代码

参考链接：https://leetcode-cn.com/problems ... istance-by-ikaruga/