题意：对一字符串，计算最少需要的添加的字符，是的该串变成回文。

分析：先求逆序，再与原串进行比较，求出最长的公共子序列 N，答案就是strlen(str)-N;

 1 code:
 2#include<iostream>
 3using namespace std;
 4
 5char str1[10006];
 6char str2[10006];
 7int len;
 8int c[10006][3];
 9
10int LCS()
11{
12     int i,j,k;
13     memset(c,0,sizeof(c));
14     for(j=1;j<=len;j++)
15     {
16         for(i=1;i<=len;i++)
17         {
18             if(str1[i-1]==str2[j-1])
19                 c[i][j%3]=c[i-1][(j-1+3)%3]+1;
20             else if(c[i-1][j%3]>=c[i][(j-1+3)%3])
21                 c[i][j%3]=c[i-1][j%3];
22             else c[i][j%3]=c[i][(j-1+3)%3];
23         }
24     }
25     return c[len][(len)%3];
26}
27
28int main()
29{
30    int i,j,k;
31    while(EOF!=scanf("%d",&len))
32    {
33        scanf("%s",str1);
34
35        for(i=0;i<len;i++)
36            str2[i]=str1[len-i-1];
37        
38        k=LCS();
39        printf("%d\n",len-k);
40    }
41    return 0;
42}