问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1159思路:
看完题目，完全不知道该怎么做
参考discuss，发现原来DP这么这么地强大，自己那是相当菜
设ch[1]..ch[n]表示字符串1至n位，i为左游标，j为右游标 ，则i从n递减，j从i开始递增。
min[i][j]表示i和j之间至少需要插入多少个字符才能对称,初始置全0 ,我们最终需要得到的值是min[1][n].
则
if(ch[i]==ch[j]) //如果两个游标所指字符相同，向中间缩小范围
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 +（min[i+1][j]和min[i][j-1]中的较小值）; //如果不同，典型的状态转换方程额，状态方程看明白了，结果发现代码居然不知道怎么写...那个汗哪...
原因是没有发现当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 }