跳转至

516. 最长回文子序列

力扣链接(中等)：https://leetcode.cn/problems/longest-palindromic-subsequence

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

个人题解

本题和 647. 回文子串 不同，虽然都是求回文串，但一个是子串，一个是子序列，二者是完全不同的，所以递推公式也有所区别。

不难给出 dp 数组定义：dp[i][j] 代表区间为 [i, j] 的子串中最长回文子序列的长度。

大体思路还是类似，都是判断首尾是否相等，如果相等，则在首尾之间的区间状态 dp[i + 1][j - 1] 的基础上 +2，因为首尾各占一个长度；如果首尾不相等，代表首尾这两个元素无法组合为回文串，所以需要抛弃掉左边界或者右边界，即 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])，这里为什么没有取 dp[i - 1][j - 1]，因为一定满足 dp[i + 1][j], dp[i][j - 1] >= dp[i - 1][j - 1]。

这里需要注意，如果首尾是同一个元素，即区间为 [i, i]，则要特殊处理，代表这个子串长度为 1，所以最长回文子序列也一定为 1。

对于遍历顺序，分析方法和 647. 回文子串 一致，这里不再赘述。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        const int N = 1010;
        int dp[N][N] = {};

        // 区间为 [i, i] 时，dp 一定为 1
        for(int i = 0; i < s.size(); i++) dp[i][i] = 1;

        // 下面处理子串长度 > 1 的情况
        for(int i = s.size(); i >= 0; i--) {
            // 这里排除掉了 [i, i] 这种区间的情况，解决了 [j - 1] == -1 的越界风险
            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];
    }
};