给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子1:
abcda google
输出例子1:
2 2
思路：先求解出原先字符串的最大回文串长度
基本思路：最大回文串长度=原先串str1与翻转串str2 的最大公共子序列长度
采用动态规划求解最大公共子序列长度即可
#include<iostream> #include<string> using namespace std; int dp[1000][1000];//dp[i][j]表示str 串前i部分与 str2 串 前j部分的最长子序列长度 int max_res(string str) { for(int i=0;i<1000;i++) { dp[0][i]=0; dp[i][0]=0; } string str2; for(int i=0;i<str.size();i++) str2+=str[str.size()-i-1]; //求解str中的最长回文串长度 相当于将原先串 翻转串 求最长子序列 int size1=str.size(); int size2=str2.size(); for(int i=1;i<=size1;i++) for(int j=1;j<=size2;j++) { if(str[i-1]==str2[j-1]) //两个字符相等 dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } return dp[size1][size2]; } int main() { string str; while(cin>>str) { int max_=max_res(str); cout<<str.size()-max_<<endl; } return 0; }
