题意：输入一个字符串，至少插入几个字符可以变成回文串（左右对称的字符串）
分析：f[x][y]代表x与y个字符间至少插入f[x][y]个字符可以变成回文串，可以利用动态规划的思想，求解
状态转化方程：
f[x][y]=0 初始化
f[x][y]=f[x+1][y-1] s[x]==s[y]时
f[x][y]=MIN ( f[x+1][y] , f[x][y-1] )+1 s[x] != s[y]时
代码展示
一开始没有将算的的数据存放到数组中，使得有些数据重复计算好多次，TLE 。 f[x][y]可以记录值
空间复杂度挺高的，f数组仅仅用到一半的存储空间，可以通过x与y计算，将二维数组转换成一维数组 f[(max+1)*max/2]
// hdu 1159 Palindrome 49392K 1797MS
#include<iostream>
#include<cstdio>
#define MIN(a,b) ((a)>(b)?(b):(a))
using namespace std;
char s[];
short f[][];//存放区间内插入最小字符个数
int result(int be, int fi)
{
if(f[be][fi]!=-)return f[be][fi]; //已求出最小值
else if(be>=fi)return ; //代表结束
else if(s[be] == s[fi]) return f[be][fi] = result(be+,fi-);
else
{
int t1 = result(be,fi-);
int t2 = result(be+,fi);
return f[be][fi]=MIN(t1,t2)+;
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=; i<=n; i++)
cin >> s[i];
memset(f,-,sizeof(f));
cout << result(,n)<<endl;
}
return ;
}
经典典型动态规划代码（没有重复计算）每次计算用到的数据都是前面计算得到的结果，没有冗余
对于计算结果f[x][y] 由于计算结果总是与f[x+1][y-1]、f[x+1][y]、f[x][y-1]三个变量有关联 因而 x 从后往前开始循环，y从x向后开始循环
// hdu 1159 Palindrome 40708K 344MS
#include<iostream>
#include<cstdio>
#define MIN(a,b) ((a)>(b)?(b):(a))
using namespace std;
char s[];
short f[][];
int main()
{
int n,i,j;
while(cin >> n >> s+)
{
for(i=n; i>0; i--)
for(j=i+1; j<=n; j++)
if(s[i] == s[j]) f[i][j]=f[i+1][j-1];
else f[i][j] = MIN(f[i+1][j], f[i][j-1])+1;
cout << f[][n] << endl;
}
return ;
}