目录
力扣516. 最长回文子序列
难度 中等
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
class Solution {
public:
int longestPalindromeSubseq(string s) {
}
};解析代码
状态表示：
关于单个字符串问题中的回文子序列，或者回文子串，我们的状态表示研究的对象一般都是选取原字符串中的用段区域 [i, j] 内部的情况。这里继续选取字符串中的一段区域来研究：
dp[i][j] 表示：s 字符串 [i, j] 区间内的所有的子序列中，最长的回文子序列的长度
状态转移方程： 关于回文子序列和回文子串的分析方式，一般都是比较固定的，都是选择这段区域的左右端点的字符情况来分析。因为如果一个序列是回文串的话，去掉首尾两个元素之后依旧是回文串，首尾加上两个相同的元素之后也依旧是回文串。因为，根据首尾元素的不同，可以分为下面两种情况：
- 当首尾两个元素相同的时候，也就是 s[i] == s[j] ：那么 [i, j] 区间上的最长回文子序列，应该是 [i + 1, j - 1] 区间内的那个最长回文子序列首尾填上 s[i] 和 s[j] ，此时dp[i][j] = dp[i + 1][j - 1] + 2
- 当首尾两个元素不相同的时候，也就是 s[i] != s[j] ：此时这两个元素就不能同时添加在一个回⽂串的左右，那么我们就应该让 s[i] 单独加在⼀个序列的左边，或者让 s[j] 单独放在⼀个序列的右边，看看这两种情况下的最大值：
单独加入 s[i] 后的区间在 [i, j - 1] ，此时最长的回文序列的长度就是 dp[i][j - 1] ；
单独加入 s[j] 后的区间在 [i + 1, j] ，此时最长的回文序列的长度就是 dp[i+ 1][j] ；
取两者的最大值，于是 dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) ;
综上所述，状态转移方程为：
- 当 s[i] == s[j] 时： dp[i][j] = dp[i + 1][j - 1] + 2 ;
- 当 s[i] != s[j] 时： dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) ;
初始化、填表顺序、返回值：
根据状态转移方程 dp[i][j] = dp[i + 1][j - 1] + 2 ，状态表示的时候，选取的是⼀段区间，因此需要要求左端点的值要小于等于右端点的值，因此会有两种边界情况：
- 当 i == j 的时候， i + 1 就会大于 j - 1 ，此时区间内只有一个字符。这个比较好分析， dp[i][j] 表示一个字符的最长回文序列，一个字符能够自己组成回文串，因此此时 dp[i][j] = 1 ;
- 当 i + 1 == j 的时候， i + 1 也会大于 j - 1 ，此时区间内有两个字符。这样也好分析，当这两个字符相同的时候， dp[i][j] = 2 ; 不相同的时候， d[i][j] = 0 ;
对于第一种边界情况，在填表的时候就可以同步处理。 对于第二种边界情况， dp[i + 1][j -1] 的值为 0 ，不会影响最终的结果，因此可以不用考虑。
dp[i + 1] 表示下一行的位置， dp[j - 1] 表示前一列的位置，所以从下往上填表，返回dp[0][n - 1];
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
// dp[i][j] 表示：s 字符串 [i, j]区间内的所有的子序列中，最长的回文子序列的长度
for(int i = n - 1; i >= 0; --i) // 枚举左端点i
{
dp[i][i] = 1; // i等于j的情况
for(int j = i + 1; j < n; ++j) // 枚举右端点j
{
if(s[i] == s[j]) // dp[i + 1][j - 1] 无效就是0
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
};