最长回文子序列
和647类似
动态规划
- 确定dp数组（dp table）以及下标的含义
dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。 - 确定递推公式
在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。
如果s[i]与s[j]相同，
- j - i ==0 , dp[i][j] = 1;
- j - i == 1, dp[i][j] = 2;
- j - i > 2, dp[i][j] = dp[i + 1][j - 1] + 2;
- 如果s[i]与s[j]不同
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
确定遍历顺序
从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j]，
也就是从矩阵的角度来说，dp[i][j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。
class Solution { public: int longestPalindromeSubseq(string s) { if(s.size()<=1) return s.size(); vector<vector<int>> dp(s.size() , vector<int>(s.size() ,0)); int result = 0; for(int i=s.size()-1; i>=0 ;i-- ) for(int j=i ;j<s.size();j++) { if(s[i]==s[j]) { if(j==i) dp[i][j] = 1; else if(j-i==1) dp[i][j] = 2; else dp[i][j] = dp[i+1][j-1] + 2; if(dp[i][j] > result) result = dp[i][j]; }else { dp[i][j] = max(dp[i][j-1],dp[i+1][j]); } } // for(int i=0;i<s.size();i++) // { // for(int j=0;j<s.size();j++) // cout<<dp[i][j]<<' '; // cout<<endl; // } return result; } };
二刷
class Solution { public: int longestPalindromeSubseq(string s) { vector<vector<int>> dp(s.size() , vector<int>(s.size() ,0 )); for(int i=s.size()-1 ; i>=0 ;i--) { for(int j=i ; j<s.size() ;j++) { if(s[i]==s[j]) { if(j-i == 0) dp[i][j] = 1; else if(j-i == 1) dp[i][j] = 2; else dp[i][j] = dp[i+1][j-1] +2; }else dp[i][j] = max(dp[i+1][j-1] , max(dp[i+1][j] , dp[i][j-1])); } } return dp[0][s.size()-1]; } };
