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

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

// 自底向上迭代dp，由于存在递归i 和 j到-1位置的情况，因此dp数组整体扩大一位

vector<vector<int>> dp;

int myMin(int a,int b,int c){
    return min(a,min(b,c));
}


int main(){
    string s1;
    string s2;
    cin >> s1;
    cin >> s2;
    int res = INT_MAX;
    int m = s1.size();
    int n = s2.size();
    dp = vector<vector<int>>(m+1,vector<int>(n+1,0));
    // base case
    for(int i = 1 ; i <= m ; i++ )
        dp[i][0] = i;
    for(int j = 1 ; 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] = myMin(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+1);
        }
    }

    cout << dp[m][n];


}