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

1. 编译距离，动态规划，四种情况同时取最小就行

#include<bits/stdc++.h>

using namespace std;

int main(){

    string s,t;

    while(cin>>s>>t){

        vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1,0));

        for(int i=0; i<= s.size();i++){
            dp[i][0] = i;
        }

        for(int i=0; i<= t.size();i++){
            dp[0][i] = i;
        }

        for(int i = 1; i<= s.size();i++){
            for(int j = 1; j<= t.size(); j++){
                dp[i][j] = min(dp[i-1][j]+1, min(dp[i][j-1]+1,dp[i-1][j-1]+ (s[i-1]!=t[j-1])));
            }
        }

        cout<<dp[s.size()][t.size()]<<endl;
    }


    return 0;
}