原题链接
f[i][j]记录到ai，bj时的最小编辑距离
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<ctime> #define MOD 10007 #define LL long long using namespace std; char a[2005],b[2005]; int la,lb,i,j,f[2005][2005],sa[2005],sb[2005]; int main() { scanf("%s",a); scanf("%s",b); la=strlen(a); lb=strlen(b); for(i=0;i<la;i++) sa[i+1]=(a[i]-'a')+1; for(i=0;i<lb;i++) sb[i+1]=(b[i]-'a')+1; for(i=1;i<=la;i++) f[i][0]=i; for(i=1;i<=lb;i++) f[0][i]=i; for(i=1;i<=la;i++) for(j=1;j<=lb;j++) { if(sa[i]==sb[j]) f[i][j]=f[i-1][j-1]; else f[i][j]=min(f[i-1][j-1],min(f[i][j-1],f[i-1][j]))+1; } printf("%d",f[la][lb]); return 0; }