回文字符串

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

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

1. 分析

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

2. 复杂度分析：

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. 分析

算法实现：
(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. 复杂度分析：

#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;
}