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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string s;
    string t;
    cin >> s;
    cin >> t;
    vector<vector<int>> dp(s.length() + 1, vector<int>(t.length() + 1, 0));
    for(int i = 0; i <= s.length(); i++) {
        for(int j = 0; j <= t.length(); j++) {
            if(!i || !j) {
                dp[i][j] = j + i;
                continue;
            }
            if(s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
                continue;
            }
            dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
            dp[i][j]++;
        }
    }
    cout << dp[s.length()][t.length()] << endl;
}

DP 问题，dp[i][j]表示s[0-i] t[0-j]相同，需要多少操作次数。

可以从dp[i - 1][j - 1] 替换一个s[i]或者t[j]获得。

可以从dp[i - 1][j] 添加一个s[i]获得。

可以从dp[i][j - 1]添加一个t[j]获得。