题目：
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。
如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子:
abcda google
输出例子:
2 2
#include <iostream>
#include <string>
using namespace std;
int dp[1002][1002];
int max(const int &a,const int &b)
{
return a>b?a:b;
}
int huiwen(const string &s,const int &b,const int &e)
{ //b e 表示两个串的位置
if(b>e)
{
return 0;
}
if(b==e)
{
dp[b][e]=1;
return 1;
}
if(dp[b][e]!=0)
{
return dp[b][e];
}
if(s[b]==s[e])
{
dp[b][e]=huiwen(s,b+1,e-1)+2;
}
else
{
dp[b][e]=max(huiwen(s,b+1,e),huiwen(s,b,e-1));
}
return dp[b][e];
}
int main()
{
string s;
while(cin>>s)
{
int len = s.size();
//初始化
for(int i=0; i<=len; ++i)
{
for(int j=0; j<=len; ++j)
{
dp[i][j]=0;
}
}
int ans = huiwen(s,0,len-1);//找最长子序列 正反字符串的最长公共子序列
cout<<len-ans<<endl;
}
return 0;
}
