这道题是一道对应的 动态规划 

这是大佬的题解
****************************************************************************************************************************
  1. lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离；
  2. 插入和删除操作互为逆过程：a删除指定字符变b等同于b插入指定字符变a；
  3. 如果a[i] == b[j]，则说明a[i]和b[j]分别加入a，b之后不会影响levenshtein距离，lev[i][j] = lev[i-1][j-1] + 0;
  4. 如果a[i] != b[j]，则需要考虑3种情况的可能：
    1. a中插入字符，即lev[i][j] = lev[i-1][j] + 1;
    2. b中插入字符，即lev[i][j] = lev[i][j-1] + 1;
    3. a[i]替换成b[j]，lev[i][j] = lev[i-1][j-1] + 1;
  5. 取这4种情况的最小值。
  6. *********************************************************************************************************************** 
    #include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;

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

int solve(string a,string b){
    a.insert(0,1,' ');
    b.insert(0,1,' ');

    int n = a.size(), m = b.size();
    int cost, lev[n][m];

    for(int i = 0; i < n; i++) lev[i][0] = i;
    for(int j = 0; j < m; j++) lev[0][j] = j;

    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(a[i]==b[j]) cost=0;
            else cost=1;

            lev[i][j]=findMin(lev[i][j-1]+1,lev[i-1][j]+1,lev[i-1][j-1]+cost);
        }
    }

    return lev[n-1][m-1];
}

int main()
{
    string a,b;
    cin>>a>>b;

    int ans=solve(a,b);
    cout<<ans<<endl;
    return 0;
}