简单dp
res[i][j]表示i长度的前a个字符的串与前j个长度的b字符串的编辑距离
当stra[i-1]等于strb[j-1]时,状态转移为res[i][j]=res[i-1][j-1]
否则,res[i][j]=MIN(res[i-1][j-1]+1,res[i][j-1]+1,res[i-1][j]+1)
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; char stra[1010]; char strb[1010]; int res[1010][1010]; //res[i][j]表示i长度的前a个字符的串与前j个长度的b字符串的编辑距离 //最后结果为res[la][lb] int main() { int la,lb; while (~scanf("%d %d",&la,&lb)) { scanf("%s",stra); scanf("%s",strb); //求res[i][j] //res[i-1][j]+1 res[i][j-1]+1 res[i-1][j-1] for (int i= 0; i <=lb; i++) { res[0][i]=i; } for (int i = 0; i <=la; i++) { res[i][0]=i; } for(int i=1;i<=la;i++) { for(int j=1;j<=lb;j++) { res[i][j]=INT_MAX; } } for(int i=1;i<=la;i++) { for (int j = 1; j <=lb; j++) { if(stra[i-1]==strb[j-1]) { res[i][j]=res[i-1][j-1]; } if(res[i-1][j]>res[i][j-1]) { if (res[i][j]>res[i][j-1]+1) { res[i][j]=res[i][j-1]+1; } } else { if (res[i][j]>res[i-1][j]+1) { res[i][j]=res[i-1][j]+1; } } if(res[i][j]>res[i-1][j-1]+1) { res[i][j]=res[i-1][j-1]+1; } } } printf("%d\n",res[la][lb]); } return 0; }