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

#include<iostream>

using namespace std;

int min(int a, int b, int c) {
    if (a < b) return a < c ? a : c;
    else return b < c ? b : c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int dp[s.size() + 1][t.size() + 1];
    for (int i = 0; i <= s.size(); i++) dp[i][0] = i;
    for (int j = 0; j <= t.size(); j++) dp[0][j] = j;
    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], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
        }
    }
    cout << dp[s.length()][t.length()];
    return 0;
}