C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n1,n2,f[N];
char a[N],b[N];

int main(){
    ios::sync_with_stdio(false);
    cin>>n1;
    cin>>(a+1);
    cin>>n2;
    cin>>(b+1);
    for(int i=0;i<=n2;++i) f[i]=i;
    for(int i=1;i<=n1;++i){
        int last=i,pre=f[0];
       // for(int k=0;k<=n2;++k) cout<<f[k]<<" ";
       // cout<<endl;
        for(int j=1;j<=n2;++j){
            int t=f[j];
            f[j]=min(last+1,f[j]+1);
            if(a[i]==b[j]) f[j]=min(f[j],pre);
            else f[j]=min(f[j],pre+1);
            last=f[j];
            pre=t;
        }

        f[0]=i;
    }
    cout<<f[n2]<<endl;
}