代码随想录算法训练营第四十三天| 583. 两个字符串的删除操作 72. 编辑距离

 1 // 要求：两个字符串，删除任意一个字符后，让这两个字符相等
 2 // dp[n][m] 以n-1结尾的字符串变成节点为m-1为子序列的最大个数
 3 // 
 4 // 求最大相同子序列长度
 5 // 和上一个的区别：不光s[i-1]忽略 t[j-1] 也可以忽略
 6 // 
 7 // dp[i][j] 
 8 //   相等 dp[i-1][j-1]+1
 9 //   不相等 max(dp[i-1][j],dp[i][j-1])
10 //
11 int minDistance(string word1, string word2) {
12     vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
13 
14 
15     for (int i = 1; i <= word1.size(); i++)
16     {
17         for (int j = 1; j <= word2.size(); j++)
18         {
19             if (word1[i - 1] == word2[j - 1])
20             {
21                 dp[i][j] = dp[i - 1][j - 1] + 1;
22             }
23             else
24             {
25                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
26             }
27         }
28     }
29 
30     int result = word1.size() - dp[word1.size()][word2.size()] + word2.size() - dp[word1.size()][word2.size()];
31 
32     return result;
33 }