题目: 给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子:
abcda google
输出例子:
2 2
思路:先求解原字符串的逆置串，再求解原字符串与逆置串的最长公共子序列长度(LCS),在用原长度减去LCS长度，就可以求得结果。
求解逆置串很简单，求解最长公共子序列也是很常见的问题，常用动态规划的方法求解。代码如下:
#include <bits/stdc++.h> using namespace std; const int MAXN=1010; int dp[MAXN][MAXN]; class Solution { public: int LDP(string str1) { string copystr = ""; for (string::reverse_iterator rit = str1.rbegin(); rit != str1.rend(); ++rit) { copystr += *rit; } string str2 = copystr; memset(dp,0,sizeof(dp)); int m = str1.size(); int n = str2.size(); int i, j; for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else if (dp[i - 1][j] > dp[i][j - 1]) { dp[i][j] = dp[i - 1][j]; } else dp[i][j] = dp[i][j - 1]; } } return (m - dp[i - 1][j - 1]); } }; int main() { string s; while(cin>>s) { Solution solution; cout<<solution.LDP(s)<<endl; } return 0; }