51Nod 1183 编辑距离 (DP)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1183

比较经典的问题，题意不多说了。跟最长公共子序列(LCS)类似。

dp[i][j]表示a字符串0~i-1，b字符串0~j-1最少编辑次数。

要是a[i] == b[j]的话，此时就不用改变，dp[i][j] = dp[i - 1][j - 1]

否则dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

 1 //#pragma comment(linker, "/STACK:102400000, 102400000")
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <ctime>
10 #include <list>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long LL;
15 typedef pair <int, int> P;
16 const int N = 1e3 + 5;
17 int dp[N][N];
18 char a[N], b[N];
19 
20 int main()
21 {
22     while(cin >> a >> b) {
23         int n = strlen(a), m = strlen(b);
24         //下面两个for初始化
25         for(int i = 1; i <= n; ++i) {
26             if(a[i - 1] == b[0])
27                 dp[i][1] = i - 1;
28             else
29                 dp[i][1] = min(dp[i - 1][1] + 1, i);
30         }
31         for(int i = 1; i <= m; ++i) {
32             if(b[i - 1] == a[0])
33                 dp[1][i] = i - 1;
34             else
35                 dp[1][i] = dp[1][i - 1] + 1;
36         }
37         for(int i = 2; i <= n; ++i) {
38             for(int j = 2; j <= m; ++j) {
39                 if(a[i - 1] == b[j - 1]) {
40                     dp[i][j] = dp[i - 1][j - 1];
41                 } else {
42                     dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
43                 }
44             }
45         }
46         cout << dp[n][m] << endl;
47     }
48     return 0;
49 }