分析：由于回文是向右和向左读的都是一样的，那么我们可以这样思考，建立另一个数组，该数组是原数组的反方向的，那么假设两者读的都是一样的，那么这两者就是相同的，也就是说他们两者组合成了回文，因此题目就化为了求最长公共子序列的问题了

code：

1. #include<stdio.h>
2. #include<climits>
3. #include<algorithm>
4. #include<stack>
5. #include<iostream>
6. #include<cmath>
7. #include<set>
8. #include<vector>
9. #include<map>
10. #include<queue>
11. #include<string.h>
12. using namespace std;
13. const int maxn=10000;
14. int c[2][maxn];
15. char str1[maxn];
16. char str2[maxn];
17. int main( void )
18. {
19. int n;
20. while (scanf( "%d" ,&n)!=EOF)
21. {
22. memset(c,0, sizeof (c));
23. getchar();
24. for ( int i=1;i<=n;i++)
25. {
26. scanf( "%c" ,&str1[i]);
27. str2[n-i+1]=str1[i];
28. }
29. int flag=1;
30. for ( int i=1;i<=n;i++)
31. {
32. for ( int j=1;j<=n;j++)
33. {
34. if (str1[i]==str2[j])
35. {
36. c[flag][j]=c[1-flag][j-1]+1;
37. }
38. else
39. {
40. c[flag][j]=max(c[flag][j-1],c[1-flag][j]);
41. }
42. cout<<c[flag][j]<< " " ;
43. }
44. cout<<endl;
45. flag=1-flag;
46. }
47. cout<<c[1-flag][n]<<endl;
48. }
49. return 0;
50. }

滚动数组优化空间

另外我查阅资料更新本文章的另一种方案，可以模拟一下，本算法不是很难的：

通过前面的分析我们很容易想到这样的算法：
对于一个序列 S 只要看它的左右端的字符是否相同，如果相同那么就看除掉两端字符的新串
要添的字符个数了；如果不同，就在它左面添上右断的字符然后考虑去掉新序列两端的字符
后的串要添的字符。或者在右面添上左端的字符，在考虑去掉添了字符后新串左右两端字符
得到的新串要添的字符。
设计一个二维状态 opt[L,i]表示长度是 L+1，起点是 i 的序列变成回文词要添的字符的个数。
阶段就是字符的长度，决策要分类，即 S[i]  和 S[i+L]是否相等。
状态转移方程:
min(opt[L-1,i]+1, opt[L-1,i+1]+1)           (s[i]<>s[i+L])
opt[L,i]=
min(opt[L-1,i]+1, opt[L-1,i+1]+1,opt[L-2,i+1])   (s[i]=s[i+L])
复杂度：
空间复杂度=状态数 O（N2）
时间复杂度=状态数 O（N2）*  转移代价 O（1）=O（N2）
由于空间复杂度较高，仍然要用滚动数组

青藤工作室在本周进行了第一次面试，简单说了一下寒假作业，进行了简短的交流。然后综观所有，找出了一些特别好看的作品给我们参观，网址为http://47.106.199.169（时间过长，网址可能会失效）。这些人的作品都很好看，艺术细胞较少的我没有上去也心服口服，但我依然会努力。青藤工作室依然是我最喜欢的工作室，现在也只做这个工作室的作业了。现在已经发布了新一阶段的作业。简单的说就是在三个月的时间内把... 回文 词是一种对称的 字符 串——也就是说，一个 回文 词，从左到右读和从右到左读得到的结果是一样的。任意给定一个 字符 串，通过插入若干 字符 ，都可以变成一个 回文 词。你的任务是写一个程序，求出将给定 字符 串变成 回文 词所需插入的 最少 字符 数。 比如 字符 串“Ab3bd”，在插入两个 字符 后可以变成一个 回文 词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的 字符 无法使它变成一个 回文 词。输入格式 回文 词是一种对称的 字符 串——也就是说，一个 回文 词，从左到右读和从右到左读得到的结果是一样的。任意给定一个 字符 串，通过插入若干 字符 ，都可以变成一个 回文 词。你的任务是写一个程序，求出将给定 字符 串变成 回文 词所需插入的 最少 字符 数。比如 字符 串“Ab3bd”，在插入两个 字符 后可以变成一个 回文 词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的 字符 无法使它变成一个 回文 词。 给出一个 字符 串求出使其变... 题目描述： 给定一个 字符 串S，可以通过在 字符 串的任意位置插入 字符 ，使其变为 回文 串。求 最少 插入 字符 的数量。 题目来源：https://vjudge.net/problem/POJ-1159 求出S中，是 回文 的最长子序列L，那么结果ans = length(S) - length(L)，解法如下：      1. 求出S的逆序串S‘      2. 求出S和S’的最长公共子序 回文 词(palin.pas/c/cpp)【问题描述】 回文 词是一种对称的 字符 串——也就是说，一个 回文 词，从左到右读和从右到左读得的结果是一样的。任意给定一个 字符 串，通过插入若干 字符 ，都可以变成一个 回文 词。你任务是写一个程序，求出将给定 字符 串变成 回文 词所需插入的 最少 字符 数。比如 字符 串“Ab3bd” ，在插入两个 字符 后可以变成一个 回文 词（ “dAb3bAd”“Adb3bdA” ） 。然而，插入两个以下的字