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

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

int main() {
    string s,t;
    cin>>s>>t;
    vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
    for (int i = 1; i <= s.size(); i++) dp[i][0] = i;
    for (int i = 1; i <= t.size(); i++) dp[0][i] = i;
    for (int i = 1; i <= s.size(); i++){
        for (int j = 1; j <= t.size(); j++){
            if (s[i - 1] == t[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            }
            else {
                dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            }
        }
    }
    cout << dp[s.size()][t.size()];
}
// 64 位输出请用 printf("%lld")