问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3356思路:
与最长公共子序列挺相似的一道动态规划
if(first[i] == second[j])
f(i, j) = min(f(i-1, j-1)[nothing], f(i-1, j)+1[deletion], f(i, j-1)+1[insertion])
else
f(i, j) = min(f(i-1, j-1)+1[change], f
(i-1, j)+1[deletion], f(i, j-1)+1[insertion])
其中，f(i, j)表示使first[0..i]转化成second[0..j]所需要的最小操作数
一个需要注意的问题是table的初始化，一开始想当然地将table[i][0], table[0][j]初始化为无穷大，导致出错
这可以说是一个普遍化的问题，就是要
注意动态规划时的初始化 1 int
2 dfs()
3 {
4 int i, j;
5 /* Attention: initialize */
6 /* set table[i][0] and table[0][j] to INT_MAX, which caused WA */
7 for(i=0; i<=m; i++)
8 table[i][0] = i;
9 for(j=0; j<=n; j++)
10 table[0][j] = j;
11 for(i=1; i<=m; i++) {
12 for(j=1; j<=n; j++) {
13 if(x[i-1] == y[j-1])
14 table[i][j] = min(table[i-1][j-1], table[i-1][j]+1, table[i][j-1]+1);
15 else
16 table[i][j] = min(table[i-1][j-1], table[i-1][j], table[i][j-1]) + 1;
17 }
18 }
19 return table[m][n];
20 }