1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<cstdio> 5 #include<algorithm> 6 using namespace std; 7  8 const int maxn = 1000 + 5; 9 10 int n1, n2;11 char s1[maxn], s2[maxn];12 int d[maxn][maxn];13 14 int main()15 {16     //freopen("D:\\txt.txt", "r", stdin);17     while (cin >> n1)18     {19         cin >> s1 + 1 >> n2 >> s2 + 1;20         memset(d, 0, sizeof(d));21         for (int i = 1; i <= n1; i++)22             d[i][0] = i;23         for (int i = 1; i <= n2; i++)24             d[0][i] = i;25         for (int i = 1; i <= n1; i++)26         for (int j = 1; j <= n2; j++)27         {28             if (s1[i] == s2[j])  d[i][j] = d[i - 1][j - 1];29             else30                 d[i][j] = min(d[i - 1][j] + 1, min(d[i][j - 1] + 1, d[i - 1][j - 1] + 1));31         }32         cout << d[n1][n2] << endl;33     }34 }