第 20 题 （编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。 #in

1. #include <iostream> 
2. #include <string> 
3. #include <vector> 
4. using namespace std; 
5. int min(int x, int y, int z) { 
6.     return min(min(x, y), z); 
7. } 
8. int edit_dist_dp(string str1, string str2) { 
9.     int m = str1.length(); 
10.     int n = str2.length(); 
11.     vector<vector<int>> dp(m + 1, vector<int>(n + 1)); 
12.     for (int i = 0; i <= m; i++) { 
13.         for (int j = 0; j <= n; j++) { 
14.             if (i == 0) 
15.                 dp[i][j] = ①; 
16.             else if (j == 0) 
17.                 dp[i][j] = ②; 
18.             else if (③) 
19.                 dp[i][j] = ④; 
20.             else 
21.                 dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤); 
22.         } 
23.     } 
24.     return dp[m][n]; 
25. } 
26. int main() { 
27.     string str1, str2; 
28.     cin >> str1 >> str2; 
29.     cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl; 
30.     return 0; 
31. }