题目描述
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
Example 1:
输入：s = “bbbab” 输出：4 解释：一个可能的最长回文子序列为 “bbbb” 。
Example 2:
输入：s = “cbbd” 输出：2 解释：一个可能的最长回文子序列为 “bb” 。
Constraints:
- 1 <= s.length <= 1000
- s 仅由小写英文字母组成
解题思路
- dp数组，后面的状态可由前面的状态进行转移。
- 当s[i] = s[j]时，dp[i][j] = dp[i + 1][j - 1] + 2
- 否则，让其等于两者dp[i + 1][j], dp[i][j + 1]中的max即可
- 注意，这里的i要从后面往前进行推导，由上面的分析可得dp[i][j]依赖于dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1]。如果从头往前开始遍历的话，会出现这三个状态空值的情况（可以试着跟着流程走一下）
C++代码
class Solution {
public:
int longestPalindromeSubseq(string s) {
int size = s.size();
if(size == 0){
return 0;
}
vector<vector<int>> dp(size, vector<int>(size, 0));
for(int i = 0; i < size; i++){
dp[i][i] = 1;
}
// int ans = 1;
for(int i = s.size() - 1; i >= 0; i--){
for(int j = i + 1; j < s.size(); j++){
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]);
}
// ans = max(ans, j - i + 1);
}
}
return dp[0][size - 1];
}
};
