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