题目描述

给定一个字符串 s，找到其中最长的回文子序列。可以假设 s 的最大长度为 1000。

样例

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

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

限制

• 1 <= s.length <= 1000
• s 只包含小写英文字母。

算法

(动态规划) $O(n^2)$

1. 设状态 $f(i, j)$ 表示闭区间 [i, j] 的最长回文子序列。
2. 初始时 $f(i, i) = 1$，其余待定。
3. 每次 $f(i, j)$ 有两种转移，若 $s(i) = s(j)$，则 $f(i, j) = f(i + 1, j - 1) + 2$；否则 $f(i, j) = \max (f(i + 1, j), f(i, j - 1))$。
4. 最终答案为 $f(0, n - 1)$。

时间复杂度

• 状态数为 $O(n^2)$，转移时间为 $O(1)$，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n^2)$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> f(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++)
            f[i][i] = 1;

        for (int len = 2; len <= n; len++)
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (s[i] == s[j])
                    f[i][j] = f[i + 1][j - 1] + 2;
                else
                    f[i][j] = max(f[i + 1][j], f[i][j - 1]);
            }

        return f[0][n - 1];
    }
};