题解 | 计算字符串的编辑距离

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
//动态规划是用二维思维去解决二维问题
/*步骤：
1.问题结构分析
2.递推关系建立-构建状态转移方程例如：dp[i] = dp[i-1] + dp[i-2]
3.自底向上计算
4.最优方案追踪
*/
int main() {
    string str1, str2;
    while (cin >> str1 >> str2) { // 注意 while 处理多个 case
        vector<vector<int>>dp(str1.size() + 1, vector<int>(str2.size() + 1, 0));
        for (int i = 1; i < str1.size() + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j < str2.size() + 1; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i < str1.size() + 1; i++) {
            for (int j = 1; j < str2.size() + 1; j++) {
                int left = dp[i - 1][j] + 1;
                int right = dp[i][j - 1] + 1;
                int chan = dp[i - 1][j - 1];
                if (str1[i-1] != str2[j-1]) {
                    chan ++;
                }
                dp[i][j] = min(min(left, right), chan);
            }
        }

        cout << dp[str1.size()][str2.size()];
    }
}