编辑距离

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s1, s2;
int dp[2005][2005];
int n, m;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s1 >> s2;
    n = s1.length();
    m = s2.length();
    for (int i = 1; i <= max(n, m); i++)
        dp[i][0] = dp[0][i] = i;
    //s1的前i个
    for (int i = 1; i <= n; i++)
        //s2的前j个
        for (int j = 1; j <= m; j++)
            //比较s1的第i个与s2的第j个
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min(dp[i - 1][j - 1],
                                   min(dp[i - 1][j], dp[i][j - 1]));
    cout << dp[n][m] << endl;
    return 0;
}