問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1159思路:
看完題目，完全不知道該怎么做
參考discuss，發(fā)現(xiàn)原來DP這么這么地強大，自己那是相當(dāng)菜
設(shè)ch[1]..ch[n]表示字符串1至n位，i為左游標(biāo)，j為右游標(biāo) ，則i從n遞減，j從i開始遞增。
min[i][j]表示i和j之間至少需要插入多少個字符才能對稱,初始置全0 ,我們最終需要得到的值是min[1][n].
則
if(ch[i]==ch[j]) //如果兩個游標(biāo)所指字符相同，向中間縮小范圍
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 +（min[i+1][j]和min[i][j-1]中的較小值）; //如果不同，典型的狀態(tài)轉(zhuǎn)換方程額，狀態(tài)方程看明白了，結(jié)果發(fā)現(xiàn)代碼居然不知道怎么寫...那個汗哪...
原因是沒有發(fā)現(xiàn)當(dāng)i>j時，min[i][j] = 0
代碼(記憶化搜索):
1 /* Time: 1594MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 5001
6 char str[MAX_LEN+1];
7 int len;
8 short memory[MAX_LEN][MAX_LEN];
9
10 /*
11 * f[i][j] represent the minimal insert for str[i..j]
12 *
13 * f[i][j] = f[i+1][j-1], if str[i]==str[j], otherwise
14 * f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
15 */
16 int
17 func(int i, int j)
18 {
19 int a, b;
20 if(i >= j)
21 return 0;
22 if(memory[i][j])
23 return memory[i][j];
24 if(str[i] == str[j])
25 memory[i][j] = func(i+1, j-1);
26 else {
27 a = func(i+1, j);
28 b = func(i, j-1);
29 memory[i][j] = a<b ? a+1 : b+1;
30 }
31 return memory[i][j];
32 }
33
34 int
35 main(int argc, char **argv)
36 {
37 while(scanf("%d", &len) != EOF) {
38 memset(memory, 0, sizeof(memory));
39 scanf("%s", str+1);
40 printf("%d\n", func(1, len));
41 }
42 }
代碼(dp):
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 5001
5 char str[MAX_LEN];
6 int len;
7 short table[MAX_LEN][MAX_LEN];
8
9 short
10 dp()
11 {
12 int i, j;
13 /* if i>j, then table[i][j] = 0 */
14 for(i=len-1; i>=1; i--) {
15 for(j=i; j<=len; j++) {
16 if(str[i] == str[j])
17 table[i][j] = table[i+1][j-1];
18 else
19 table[i][j] = table[i+1][j]<table[i][j-1] ? table[i+1][j]+1 : table[i][j-1]+1;
20 }
21 }
22 return table[1][len];
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 while(scanf("%d", &len) != EOF) {
29 memset(table, 0, sizeof(table));
30 scanf("%s", str+1);
31 printf("%d\n", dp());
32 }
33 }