算法

C++ 代码

#include<iostream>
using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;++i)

const int N=1010;
int f[N][N];
char a[N],b[N];
int n,m;
int main(){
    scanf("%d\n%s",&n,a+1);
    scanf("%d\n%s",&m,b+1);

    ffor(i,0,n+1) f[i][0]=i;
    ffor(j,0,m+1) f[0][j]=j;

    ffor(i,1,n+1) ffor(j,1,m+1){
        f[i][j]=min(min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+(a[i]!=b[j]));
    }

    cout<<f[n][m]<<endl;
    return 0;
}

或者写成函数形式

#include<cstring> //包含 strlen
int f[N][N];
int dis(char a[],char b[]){
    int la=strlen(a+1),lb=strlen(b+1);

    ffor(i,0,la+1) f[i][0]=i;
    ffor(j,0,lb+1) f[0][j]=j;

    ffor(i,1,la+1)ffor(j,1,lb+1){
        f[i][j]=min(min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+(a[i]!=b[j]));
    }

    return f[la][lb];
}