http://poj.org/problem?id=3356
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4 int l1,l2;
5 char x[1002],y[1002];
6 int resu[1002][1002];
7 int max(int a,int b)
8 {
9 return a>b?a:b;
10 }
11 int min(int a,int b)
12 {
13 return a<b?a:b;
14 }
15
16 int main()
17 {
18 while(scanf("%d%s%d%s",&l1,x,&l2,y)!=EOF){
19
20 int i,j;
21 for(i=0;i<=max(strlen(x),strlen(y));i++){
22 resu[i][0]=i;
23 resu[0][i]=i;
24 }
25 for(i=1;i<=l1;i++)
26 for(j=1;j<=l2;j++){
27 if(x[i-1]==y[j-1])
28 resu[i][j]=resu[i-1][j-1];
29 else resu[i][j]=min(resu[i-1][j]+1,min(resu[i][j-1]+1,resu[i-1][j-1]+1));
30 }
31 printf("%d\n",resu[l1][l2]);
32 }
33 }