Shouyu

Appearance

最长回文子序列 ​

题目描述 ​

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

题目链接：https://leetcode.cn/problems/longest-palindromic-subsequence

文章讲解：https://programmercarl.com/0516.最长回文子序列.html

思路 ​

回文子序列的回文子串的区别就在于回文子序列可以删除！

只是递推的时候有所不同。

动规五部曲 ​

1、dp 数组及下标含义 ​

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

2、递推公式 ​
  • s[i] == s[j] ,dp[i][j] = dp[i + 1][j - 1] + 2;，这里我们没有像回文子串那样讨论i == j 的情况，也没有讨论i 和 j 相差1的情况。这些我们放在初始化章节讨论。
  • s[i] != s[j]，那么说明 两者同时加入不能增加 [i,j] 区间的最长回文子序列长度，那么可以试着分别加入 s[i]、s[j] ，看看哪个能组成更长的回文子序列。 dp[i + 1][j]或者dp[i][j-1]
3、初始化 ​

因为递推的时候我们没有考虑 i == j 的情况，因此我们需要手动初始化一下。初始化为1，即一个字符的回文子序列就是本身，长度1.

那么回文子串还讨论了 i 和 j 相差1呢？我们知道这时如果套用写好的递归会是 dp[i + 1][j -1] + 2。而实际上回文子序列长度是2。所以我们把 i > j 的情况初始化为 0即可。

其余情况也初始化为0 即可，其余情况可由递推公式计算覆盖

4、确定遍历顺序 ​

左下方 正左方 正下方 。我们从下往上从左往右遍历即可

5、举例推导 ​

输入s:"cbbd" 为例，dp数组状态如图：

516.最长回文子序列3

代码实现 ​

C++
int longestPalindromeSubseq(string s) {
    vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
    for(int i = 0;i < s.size();i++) dp[i][i] = 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]);
            }
        }
    }
    return dp[0][s.size() - 1];
}