sdut 1728 编辑距离问题( dp )

思路：edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。

有如下动态规划公式：

if i == 0 且 j == 0，edit(i, j) = 0
if i == 0 且 j > 0，edit(i, j) = j
if i > 0 且j == 0，edit(i, j) = i
if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <cstdio>
 6 #include <algorithm>
 7 using namespace std;
 8 const int maxn = 2000+10;
 9 char a[maxn], b[maxn];
10 int d[maxn][maxn];
11 int _min(int a, int b)
12 {
13     return a>b ? b:a;
14 }
15 
16 int main()
17 {
18     int i, j, len_a, len_b, x;
19     while(cin>>a>>b)
20     {
21         len_a = strlen(a);
22         len_b = strlen(b);
23         d[0][0] = 0;
24         for(i = 1; i <= len_a; i++)
25             d[i][0] = i;
26         for(j = 1; j <= len_b; j++)
27             d[0][j] = j;
28         for(i = 1; i <= len_a; i++)
29             for(j = 1; j <= len_b; j++)
30             {
31                 x = 0;
32                 d[i][j] = _min(d[i-1][j] + 1, d[i][j-1] + 1);
33                 if(a[i-1] != b[j-1])
34                     x = 1;
35                 d[i][j] = _min(d[i][j], d[i-1][j-1] + x);
36             }
37             cout<<d[len_a][len_b]<<endl;
38     }
39     return 0;
40 }