题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1513
题意：将一个字符串转变为回文串的最少添加字符个数
分析：只要想到将字符串逆序后与原字符串求最长公共子序列，最少添加数为len-LCS，这题又是一道裸LCS。
这里还是要滚动数组优化空间才行。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 10010
using namespace std;
char s1[],s2[];
int dp[][];
int main()
{
int n;
while(scanf("%d",&n)>)
{
scanf("%s",s1);
for(int i=; i<=n; i++)
{
s2[i-]=s1[n-i];
}
memset(dp,,sizeof(dp));
int cur=,nxt=;
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(s1[i-]==s2[j-])
dp[nxt][j]=dp[cur][j-]+;
else
dp[nxt][j]=max(dp[nxt][j-],dp[cur][j]);
}
swap(cur,nxt);
}
printf("%d\n",n-dp[cur][n]);
}
}