两道题很相近，区别在于一个是子串，一个是子序列

• 子序列
  
• 子串
  

最长回文子序列

题目

516. 最长回文子序列 - 力扣（LeetCode）
     https://leetcode-cn.com/problems/longest-palindromic-subsequence/

解析

class Solution {
public:int longestPalindromeSubseq(string A) {//dpvector<vector<int>> a(A.size(),vector<int>(A.size(),0));//从后往前遍历，保证每个子状态已被计算for(int i=A.size()-1;i>=0;--i){//初始化a[i][i]=1;for(int j=i+1;j<A.size();++j){//状态转换方程if(A[i]==A[j]){//A[i]与A[j]相等时a[i][j]=a[i+1][j-1]+2;}else{//A[i]与A[j]不相等时a[i][j]=max(a[i+1][j], a[i][j-1]);}}}return a[0][A.size()-1];}
};

最长回文子串

题目

5. 最长回文子串 - 力扣（LeetCode）
   https://leetcode-cn.com/problems/longest-palindromic-substring/

解析

class Solution {
public:string longestPalindrome(string s) {int len=s.size();vector<vector<int>> dp(len,vector<int>(len));string ans="";//l从小到大遍历，保证子状态已经被计算for(int l=0;l<len;++l){for(int i=0;i+l<len;++i){int j=i+l;if(l==0){//判断奇数最初状态(子串长度为1),即dp[i][i]？1dp[i][j]=1;}else if(l==1){//判断偶数最初状态(子串长度为2)dp[i][j]=(s[i]==s[j]);}else{//状态转化方程dp[i+1][j-1]是回文子串且s[i]==s[j]dp[i][j]=(dp[i+1][j-1]&&s[i]==s[j]);}//更新最大值if(dp[i][j]&&l+1>ans.size()){ans=s.substr(i,l+1);}}}return ans;}
};