题目难度：二星
考察点：动态规划

方法1：暴力、二进制枚举

1. 分析

我们分析一下题意，对于每个输入的字符串s，它的子串(包括不连续的子串)有2^n个，其中n为字符串s的长度，那么我们就可以枚举这2^n个子串，判断当前枚举到子串是不是回文字符串，如果是回文字符串的话，就记录答案，并取得长度最大值进行比较，否则继续枚举。

算法实现：
(1). 写一个判断字符串是不是回文字符串的函数；
(2). 对这2^n个子串进行枚举；
(3). 如果当前枚举的字符串是回文字符串的话，就更新长度最大值ans；
(4). 输出答案ans。

2. 复杂度分析：

时间复杂度：O(2^n)
空间复杂度：O(n)

3. 代码： 

#include <bits/stdc++.h>
using namespace std;
bool check(string s) {
 int len = s.size();
 for(int i=0; i<len/2; i++)  if(s[i] != s[len-1-i]) return false;
 return true;
}
int main() {
 string s; cin>>s;
 int len = s.size(), ans = 0;
 int all = (1<<len);
 for(int i=0; i<all; i++) {
     string tmp = "";
     for(int j=0; j<len; j++) if(i&(1<<j)) tmp += s[j];
     if(check(tmp)) ans = max(ans, int(tmp.size()));
 }
 cout<<ans<<endl;
 return 0;
}

方法2：动态规划

1. 分析

由于上述算法的时间复杂度实在是太高了，所以我们要进行优化，采用动态规划的算法，我们令dp[i][j]表示区间[i,j]中包含的非连续最长回文字符串长度，那么就有如下两种情况：
(1). 如果第i个字符和第j个字符相等的话，那么dp[i][j] = dp[i+1][j-1] + 2;
(2). 如果第i个字符和第j个字符不相等的话，那么dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
所以动态转移方程已经在上述情况纵列出来了。

算法实现：
(1). 输入字符串s，并取得s的长度len
(2). 进行动态规划，即两层循环，外层循环枚举j(0<=j<len)表示以j字符串结尾，内层循环枚举i(j>i>=0)表示以i字符串开始，初始化一下dp[j][j]，因为只有一个字符，显然dp[j][j]=1,然后在内层循环中判断s[j]和s[i]是否相等，根据是否相等进行上述方法中的动态转移。
(3). 输出答案dp[0][len-1]。

2. 复杂度分析：

时间复杂度：O(n^2)
空间复杂度：O(n^2)


3. 代码： 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+5;
int dp[MAXN][MAXN];
int main() {
 string s; cin>>s;
 int len = s.size();
 for(int j=0; j<len; j++){
     dp[j][j] = 1;
     for(int i=j-1; i>=0; i--){
         if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
         else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
     }
 }
 cout<<dp[0][len-1]<<endl;
 return 0;
}