mean

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。

analyse

对于这题来说，插入字符和删除字符使其成为回文串，答案是一样的.

首先求s的反串rs，然后对s和rs求最长公共子序列，要删除的字符个数就是LCS.

time complexity

O(N^2)

 code

#include 
     
      using namespace std;const int MAXN=1010;int dp[MAXN][MAXN];class Solution{public:   int solve(string &s)   {       return s.length()-getLCS(s);   }   int getLCS(string &s1)   {       string s2(s1);       reverse(s2.begin(),s2.end());       int len=s1.length();       memset(dp,0,sizeof dp);       for(int i=0;i
      
       >s)   {       Solution solution;       cout<
       
        <