首先分析該問(wèn)題，看數(shù)據(jù)大小，應(yīng)當(dāng)是一道dp題目，本題求得是最小值

狀態(tài)分析

dp[i][j]表示，字符串A前i個(gè)字符到字符串B前j個(gè)字符的編輯距離

轉(zhuǎn)移方程：

附上Cpp代碼

#include <cstdio>
#include <iostream>
#include <cstring>
#define maxn 4003
#define maxx 0x3f3f3f3f
char a[maxn],b[maxn];
int dp[maxn][maxn];
int al,bl;
int minn(int ma,int mb,int mc){
    return std::min(std::min(ma,mb),mc);
}
int main(){
    std::cin >> a >> b;
    al = strlen(a);
    bl = strlen(b);
    for(int i=0;i<=al;++i){
        for(int j=0;j<=bl;++j){
            dp[i][j] = maxx;
        }
    }
    for(int i=0;i<=al;++i){
        dp[i][0] = i;
    }
    for(int j=0;j<=bl;++j){
        dp[0][j] = j;
    }
    for(int i=1;i<=al;++i){
        for(int j=1;j<=bl;++j){
            if(a[i-1] == b[j-1]){
                dp[i][j] = dp[i-1][j-1];
            }
            else{
                dp[i][j] = minn(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
            }
        }
    }               
    std::cout << dp[al][bl] ;
    return 0;
}