评测 f[i][j]表示a中前i个字符转化为b中前j个字符最短编辑距离。结果就应是f[l1][l2] 赋初值：a串空时，对应b中j个字符时最短距离就是j（插入j个），f[0][i]=i;(i<=l2) 同理，f[i][0]=i;(i<=l1) 转移方程：
if(a[i]==b[j]) f[i][j]=f[i-1][j-1]; else f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;说明：
f[i-1][j-1]+1 , 在a[i-1]后面插入b[j] f[i-1][j]+1 , 删除a[i] f[i][j-1]+1,在a[i]后面插入b[j]（a[i]与b[j-1]对应） #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int f[2009][2009]; char a[2009],b[2009]; int main() { scanf("%s",a+1); scanf("%s",b+1); int l1=strlen(a+1),l2=strlen(b+1); for(int i=1;i<=l1;i++) f[i][0]=i; for(int i=1;i<=l2;i++) f[0][i]=i; for(int i=1;i<=l1;i++) for(int j=1;j<=l2;j++){ if(a[i]!=b[j]) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1; else f[i][j]=f[i-1][j-1]; } printf("%d",f[l1][l2]); return 0; }