动态转移方程按三个步骤来，就是从f[i-1][j-1],f[i-1][j],f[i][j-1]+1转移过来 所以就是f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i][j-1])+1
#include<cstdio> #include<cstring> #include<iostream> using namespace std; char a[9999],b[9099]; int f[3999][3999]; int main() { gets(a); gets(b); int lena=strlen(a); int lenb=strlen(b); for(int i=0;i<lena;i++) f[i][0]=i; for(int i=0;i<lenb;i++) f[0][i]=i; for(int i=1;i<=lena;i++) { for(int j=1;j<=lenb;j++) { if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]; else{ f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1; } //printf("%d ",f[i][j]); } //printf("\n"); } printf("%d",f[lena][lenb]/*+lena-lenb*/); }