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

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

int main() {
    string s1,s2;
    cin>>s1;
    cin>>s2;
    int n1=s1.size();
    int n2=s2.size();
    vector<vector<int>> dp(n1+1,vector(n2+1,0));
    for(int i=1;i<n1+1;i++){
        dp[i][0]=i;
    }
    for(int i=1;i<n2+1;i++){
        dp[0][i]=i;
    }
    for(int i=1;i<n1+1;i++){
        for(int j=1;j<n2+1;j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }else{
			  //编辑距离等于左、上、左上编辑距离最小值+1
                dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
            }
        }
    }
    cout<<dp[n1][n2];
    return 0;
}
// 64 位输出请用 printf("%lld")