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

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

int main() {
    string s1;
    string s2;
    cin>>s1>>s2;
    int n = s1.size();
    int m = s2.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1));
    dp[0][0]= 0;

    for (int i=1; i<m+1; i++) {
        dp[0][i] = i;
    }
    for (int i=1; i<n+1; i++) {
        dp[i][0] = i;
    }

    s1 = ' '+s1;
    s2 = ' '+s2;
    for (int i=1; i<n+1; i++) {
        for (int j=1; j<m+1; j++) {
            int a = dp[i][j-1] + 1;
            int b = dp[i-1][j] + 1;
            int c = dp[i-1][j-1];
            if (s1[i]!=s2[j]) {
                dp[i][j] = min(c+1, min(a,b));                
            }else {
                dp[i][j] = min(c, min(a,b));  
            }
            
        }
    }

    cout << dp[n][m] << endl;

}
// 64 位输出请用 printf("%lld")