1 //Accepted    4100 KB    0 ms 2 //类似poj1080 3 //dp[i][j]表示s1用前i个，s2用前j个的最少匹配步数 4 //dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j-1](s1[i-1]==s2[j-1])时 or dp[i-1][j-1]+1 (s1[i-1]!=s2[j-1]时)) 5 //注意初始化条件 6 //dp[i][0]=inf; 7 //dp[0][i]=i; 8 //dp[0][0]=0; 9 #include <cstdio>10 #include <cstring>11 #include <iostream>12 using namespace std;13 const int imax_n = 1005;14 const int inf = 100000000;15 char s1[imax_n];16 int n1;17 char s2[imax_n];18 int n2;19 int dp[imax_n][imax_n];20 void Dp()21 {22     for (int i=1;i<=n1;i++)23     dp[i][0]=inf;24     for (int i=1;i<=n2;i++)25     dp[0][i]=i;26     dp[0][0]=0;27     for (int i=1;i<=n1;i++)28     {29         for (int j=1;j<=n2;j++)30         {31             if (s1[i-1]==s2[j-1])32             dp[i][j]=dp[i-1][j-1];33             else34             dp[i][j]=dp[i-1][j-1]+1;35             if (dp[i][j]>dp[i][j-1]+1)36             dp[i][j]=dp[i][j-1]+1;37         }38     }39     printf("%d\n",dp[n1][n2]);40 }41 int main()42 {43     while (scanf("%d%s%d%s",&n1,s1,&n2,s2)!=EOF)44     {45         Dp();46     }47     return 0;48 }