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

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

//动态规划
//dp[i][j]表示s1以i-1为结尾的子串与s2以j-1为结尾的子串之间的编辑距离
//若s1[i-1]==s2[j-1] 则dp[i][j]=dp[i-1][j-1]
//否则，dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;

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