今天在看飞燕之家的一个问题，原帖在这http://
问题描述：
所谓回文，就是像"acbca"或者"12966921"这样的字符串，左右对称。
现在的问题是，假如给你"abaqbaa"这样的字符串，你可以对它添加一
些字符，得到"aabaqqabaa"变成回文，一共加了3个字符。
问对于随意给的一字字符串，你最少要加多少个字符才能使它变成回文？
对于刚刚的"abaqbaa"，其实可以只加2个字符变成"aabaqabaa"就成为回
文了，2就是这个字符串的最少添加字符数目。

输入
多组测试数据，每组只有一行，就是一个字符串，串长小于1000

输出
输出最少要加的字符个数

样例输入
abaqbaab
abccba
1357351

样例输出
3
0
2
想了很久没做出来，看看答案还没看懂，下面贴着的是 ttuurr的答案
谁大概能解释一下，给点思路就好，谢谢了

#include <cstdio>
#include <cstring>
const int MAX=1000;
char s[MAX+1];
int c[2][MAX+1]; 
int main() {
    int i, j, len;
    
    while(scanf("%s", s) != EOF) {
        len=strlen(s);
        for(i=1; i<=len; i++) 
    { 
            for(j=0; j<=len; j++)           
              c[0][j]=c[1][j]; 
        
            for(j=1; j<=len; j++) 
        {                
        c[1][j]=c[1][j-1];     
                if(c[0][j] > c[1][j])
                    c[1][j]=c[0][j];
                if(s[i-1]==s[len-j] && c[1][j]<c[0][j-1]+1) 
                    c[1][j]=c[0][j-1]+1;
            }
        }
        
        printf("%d\n",len-c[1][len]);
        for(i=0; i<=len; i++)
            c[1][i]=0;
    }
    return 0;
}

[[it] 本帖最后由 xuanzilie 于 2008-7-22 22:41 编辑 [/it]]

贴个我写的
 dp..！
看我签名！

[[it] 本帖最后由 菜鸟选手 于 2008-7-23 00:18 编辑 [/it]]

既然是动态规划的问题，那我还是先不强求了，数据结构还没学好呢，谢谢了

关于DP，论坛有相应的文章


[color=white]<>

2楼的看的比较清楚。。判断回文。。。从正序的第一个开始，判断与倒叙的是不是回文，然后在前一个基础上判断下一个。。同时判断是从前还是从后面大

[[it] 本帖最后由 sunkaidong 于 2008-7-23 22:55 编辑 [/it]]

sunkaidong
 我建议你做个试试 ..~
  我写的绝对不是你说的那样 ..~