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

#include <iostream>
#include<vector>
using namespace std;
//动态规划，dp[i][j]代表将s的前i个字符转变为t的前j个字符所需要的最小编辑次数
//优化空间复杂度，只用到了左，上，左上的三个位置的记录，我们只用一个额外空间记录左上即可
int main() {
    string s,t;
    getline(cin,s);
    getline(cin,t);
    int m=s.size();
    int n=t.size();
    vector<int>dp(n+1);
    //初始化
    for(int i=0; i<=n; i++)
    {
        dp[i]=i;
    }
    //循环处理
    for(int i=1 ;i<=m; i++)
    {
        int prev=dp[0];//记录左上位置
        dp[0]=i;
        for(int j=1; j<=n; j++)
        {
            int tmp=dp[j];
            if(s[i-1]==t[j-1])
                dp[j]=prev;
            else
                dp[j]=min(prev,min(dp[j-1],dp[j]))+1;
            prev=tmp;//左上的记录右移
        }
    }
    cout<<dp[n];
    return 0;
}
// 64 位输出请用 printf("%lld")