問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3356思路:
與最長公共子序列挺相似的一道動態(tài)規(guī)劃
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]所需要的最小操作數(shù)
一個需要注意的問題是table的初始化，一開始想當然地將table[i][0], table[0][j]初始化為無窮大，導致出錯
這可以說是一個普遍化的問題，就是要
注意動態(tài)規(guī)劃時的初始化 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 }