Description
回文串是一个正读和反读都一样的字符串，比如level或者noon等等就是回文串。给你一个长度为n（ 3 <= N <= 5000. ）的字符串。问最少需要插入几个字符，能够使它变成回文串
比如字符串 “Ab3bd”可以转换成(“dAb3bAd” or “Adb3bdA”). 但需要插入最少两个字符
Sample Input
5
Ab3bd
Sample Output
2
问题分析
动态规划求解；
设ch[1]..ch[n]表示字符串1至n位；
i为左游标，j为右游标，则i从n递减，j从i开始递增。
min[i][j]表示i和j之间至少需要插入多少个字符才能对称，我们最终需要得到的值是min[1][n]。
则递归关系和初始条件
当ch[i]=ch[j] min[i][j]=min[i+1][j-1];
否则 min[i][j]=1+（min[i+1][j]和min[i][j-1]中的较小值）
心得体会：
题目不易理解，但确实是我这种新手应该多接触的动态规划问题，是区间dp题目，要将大区间化为小区间，递归关系推理是个难点，就是从两端开始，如果字符相同则两端同时缩小，若不相同，则在左端添加字符（右端缩小）或右端添加字符（左端缩小），另一个难度就是循环是i，j的迭代方式
代码：
#include<iostream>
using namespace std;
int Min(int a,int b)
{
return a<b?a:b;
}
int main()
{
int n,i,j;
cin>>n;
int min[5001][5001]={0};
char ch[5001];
for(i=1;i<=n;i++)
cin>>ch[i];
for(i=n-1;i>=0;i--)
for(j=i;j<=n;j++)
{
if(ch[i]==ch[j])
min[i][j]=min[i+1][j-1];
else min[i][j]=1+Min(min[i+1][j],min[i][j-1]);
}
cout<<min[1][n]<<endl;
return 0;
}