题目链接：http://poj.org/problem?id=1159
题意：给定一个长度为N的字符串。问你最少要添加多少个字符才能使它变成回文串。
思路：最少要添加的字符个数=原串长度-原串最长回文子串长度。对于求原串最长回文子串长度用的是DP的经典问题LCS最长公共子序列的做法。 设原串为S，原串的逆串为S‘，那么原串的最长回文子串长度=S和S'的最长公共子序列长度。 由于N的范围最大是5000，所以5000*5000的数组开不下，所以需要用到滚动数组来求。[关于原串求最长回文子串用的Manacher一直WA，实在不知道哪里写崩了？或者题目就是不能用Manacher来写？目前还没弄懂]
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = + ;
typedef long long int LL;
#define INF 0x3f3f3f3f
char str[MAXN], dstr[MAXN];
int dp[][MAXN];
int main()
{
int n, ans;
while (~scanf("%d", &n)){
scanf("%s", str + ); ans = -;
memset(dp, , sizeof(dp));
for (int i = n; i > ; i--){
dstr[i] = str[n - i + ];
}
for (int i = , k = ; i <= n; i++, k = !k){
for (int j = ; j <= n; j++){
if (str[i] == dstr[j]){
dp[k][j] = dp[!k][j - ] + ;
}
else{
dp[k][j] = max(dp[k][j - ], dp[!k][j]);
}
ans = max(ans, dp[k][j]);
}
}
printf("%d\n", n - ans);
}
return ;
}