最长回文子序列和最长回文子串

佚名 6年前 (2019-04-15) 随笔 448人围观抢沙发百度已收录

对于回文子序列，因为是不连续的肯定是不能直接枚举，那么利用动态规划。

我们可以知道对于任意字符串，如果头尾字符相同，那么字符串的最长子序列等于去掉首尾的字符串的最长子序列加上首尾；如果首尾字符不同，则最长子序列等于去掉头的字符串的最长子序列和去掉尾的字符串的最长子序列的较大者。那么转移方程：dp[i][j]=dp[i+1][j-1] + 2 if（s[i] == s[j]）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

dp[i][j]=max(dp[i+1][j],dp[i][j-1]) if （s[i] != s[j]）

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm>
using namespace std; const int maxn=1005; char s[maxn]; int dp[maxn][maxn]; int main() { scanf("%s",s); int len=strlen(s); for(int i=len-1;i>=0;i--) { dp[i][i]=1; for(int j=i+1;j<=len;j++) { if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2; else dp[i][j]=max(dp[i][j-1],dp[i+1][j]); } } printf("%d\n",dp[0][len-1]); return 0; }

最长回文子串的话，解决的方案比较多，我们还是利用动态规划去求解：

string longestPalindrome(string s) { if (s.empty()) return ""; int len = s.size(); if (len == 1)return s; int longest = 1; int start=0; vector<vector<int> > dp(len,vector<int>(len)); for (int i = 0; i < len; i++) { dp[i][i] = 1; if(i<len-1) { if (s[i] == s[i + 1]) { dp[i][i + 1] = 1; start=i; longest=2; } } } for (int l = 3; l <= len; l++)//子串长度
 { for (int i = 0; i+l-1 < len; i++)//枚举子串的起始点
 { int j=l+i-1;//终点
            if (s[i] == s[j] && dp[i+1][j-1]==1) { dp[i][j] = 1; start=i; longest = l; } } } return s.substr(start,longest); }