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

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

vector<vector<int>> memo;

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

int dp(string& s1,int i, string& s2, int j){
    // 通过dp递归函数，得到s1[0...i]和s2[0...j]的最短编辑距离（倒推）

    // base case
    if( i == -1 ) return j + 1;            // s1已经走完了，s2还剩下
    if( j == -1 ) return i + 1;            // s2已经走完了，s1还剩下

    // look up memo
    if( memo[i][j] != -1 )        // 之前已经计算过对应的编辑距离
        return memo[i][j];

    // 做选择
    if( s1[i] == s2[j] )    // 如果当前字符相等，编辑距离等于前一次的距离
        memo[i][j] = dp(s1,i-1,s2,j-1);
    else{
        memo[i][j] = myMin( dp( s1, i, s2, j - 1 ) + 1,        // 增，s1[0...i]和s2[0...j-1]已相等
                            dp( s1, i - 1, s2, j ) + 1,        // 删，s1[0...i-1]和s2[0...j]已相等
                            dp( s1, i - 1, s2, j - 1 ) + 1     // 改，s1[0...i-1]和s2[0...j-1]相等
                          );
    }

    return memo[i][j];

}

int main(){
    string s1;
    string s2;
    cin >> s1;
    cin >> s2;
    int m = s1.size();
    int n = s2.size();
    memo = vector<vector<int>>(m,vector<int>(n,-1));
    int res = dp(s1,m-1,s2,n-1);
    cout << res;
}