跳转至

516. 最长回文子系列

题目大意

给你一个字符串 s ，找出其中最长的回文子序列（不要求连续），并返回该序列的长度。

  • 样例 1
    • 输入：bbbab
    • 输出：4
  • 样例 2
    • 输入：cbbd
    • 输出：2
  • 数据范围
    • \(1\leq \text{s.length}\leq 1000\)

解答&代码

  • 定义 dp[i][j]：表示子串 s[i..j] 中最长回文子序列的长度。
  • 边界：单个字符是长度为 1 的回文子序列，所以 dp[i][i] = 1。
  • 状态转移：
    • 如果 s[i] == s[j]，那么这两个字符可以作为一对回文的首尾，所以： dp[i][j]=dp[i+1][j−1]+2dp[i][j] = dp[i+1][j-1] + 2dp[i][j]=dp[i+1][j−1]+2
    • 如果 s[i] != s[j]，只能丢弃一边： dp[i][j]=max⁡(dp[i+1][j],dp[i][j−1])dp[i][j] = \max(dp[i+1][j], dp[i][j-1])dp[i][j]=max(dp[i+1][j],dp[i][j−1])
  • 遍历顺序：因为 dp[i][j] 依赖于 i+1，所以要从右往左枚举 i，从左往右枚举 j。
  • 答案是 dp[0][n-1]，即整个字符串的最长回文子序列长度。

时间复杂度：O(n²)
空间复杂度：O(n²)，可优化到 O(n)。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        // dp[i][j]表示从i到j之间的最长回文子系列长度
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; 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][n - 1];
    }
};