LeetCode 516. 最长回文子序列

约 5 分钟
文章信息 19 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 需加强 20-50 字节跳动 美团 阿里巴巴 快手 腾讯 猿辅导 百度 华为 拼多多 网易 商汤 虾皮 携程
标签
字符串 动态规划 动态规划经典题 子序列问题 区间动态规划问题
目录

题目描述

✅ 516. 最长回文子序列

image-20250510222956499

题意分析

题目给定一个字符串 s，要求返回它最长回文子序列的长度，不要求还原出这个子序列本身。

最关键的一个字是「子序列」。子序列允许任意删除字符，只要求剩下的字符保持原有的相对顺序，不要求连续。这一点必须和 5. 最长回文子串严格区分开：子串是一段连续区间，"bbbab" 的最长回文子串是 "bbb"，长度 3；而子序列可以跳过中间的 'a'，把四个 'b' 全部留下，得到 "bbbb"，长度 4。凡是「子串」题里常用的中心扩展、滑动窗口，在「子序列」题里都会失效，因为答案的字符不再挨在一起。

数据规模上，s 的长度不超过 1000，且只含小写字母。1000 这个量级是一个很强的信号：$O(n^2)$ 的做法约十万级运算，绰绰有余；而 $O(n^3)$ 会到十亿级，明显超时。它同时也暗示「枚举所有区间」是被允许的。

边界方面：s 至少含一个字符，所以答案下界是 1——任何单个字符本身就是长度为 1 的回文。整串完全没有重复字符时（例如 "abcde"），答案就是 1；整串本身即回文时，答案是 n。

解法：区间动态规划

核心思路

问题关键：子序列可以跳过字符，无法用中心扩展或滑动窗口；但回文的首尾必须相同，适合从区间两端做决策。

为什么选区间 DP：定义 dp[i][j] 为闭区间 s[i..j] 内最长回文子序列的长度。区间只有 $O(n^2)$ 个，避免枚举 $2^n$ 个子序列；相比把 s 与逆序串做 LCS，区间状态更直接，也更容易解释回文结构。

状态转移分两种情况：

  • 若 s[i] == s[j]，两端可以组成回文最外层，dp[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] 时，所有更短的依赖区间都已经得到最优值。两端相等时，内部最优回文加上这一对字符一定可行；若某个最优解只用了一个端点，可将与它配对的同字符替换为另一个端点，因此总存在一个同时使用两端的最优解。两端不等时，任意回文不可能同时使用它们，两个子区间已覆盖全部方案。

遍历顺序由依赖决定：i 从右向左，j 从 i + 1 向右。这样 dp[i + 1][j - 1]、dp[i + 1][j] 和 dp[i][j - 1] 在使用前都已计算。单字符区间初始化为 1，空区间保持 0。

解题步骤

面试时可按下面 5 步口述：

  1. 创建 n x n 的二维数组，令 dp[i][i] = 1。
  2. 从 i = n - 1 倒序枚举左端点。
  3. 从 j = i + 1 正序枚举右端点，保证先算短区间。
  4. 两端相等时取内部答案加 2；不等时取舍弃左端或右端后的较大值。
  5. 返回整个区间的答案 dp[0][n - 1]。

例如 "bbbab"：区间 "bab" 两端相等，得到 3；扩展到整串时，首尾 'b' 仍相等，内部 "bba" 的答案为 2，所以最终得到 4，对应子序列 "bbbb"。

代码实现

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for i := n - 1; i >= 0; i-- {
        dp[i][i] = 1
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else if dp[i+1][j] > dp[i][j-1] {
                dp[i][j] = dp[i+1][j]
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[0][n-1]
}

复杂度分析

  • 时间复杂度：$O(n^2)$。上三角的每个区间只计算一次。
  • 空间复杂度：$O(n^2)$。二维表保存所有区间答案；可以压到 $O(n)$，但更新顺序更易出错，面试中二维写法更清晰。

关键点总结

  • “子序列”不要求连续；中心扩展解决的是回文子串，不能套用到本题。
  • 状态定义必须明确为“区间内的答案”，最终返回 dp[0][n - 1]。
  • 转移方程写完后再确定遍历方向：依赖下一行，所以左端点必须倒序。
  • dp[i][i] = 1 是奇数长度回文的基础；下三角默认 0 可自然表示空区间。

易错点总结

  • 把左端点 i 正序枚举会读到尚未计算的 dp[i + 1][...]，例如 "bbbab" 会得到偏小结果。
  • 漏掉 dp[i][i] = 1，单字符答案会变成 0，所有奇数长度回文也会少算。
  • 把子序列误当子串："bbbab" 的最长回文子串长度是 3，最长回文子序列长度是 4。
  • 两端不等时必须比较“舍弃左端”和“舍弃右端”两种方案，不能固定只取一侧。
  • 一维压缩时不能直接覆盖 dp[j - 1]；它同时承担当前行左侧值和上一行左上值，需要额外变量保存旧值。

相似题目

题目 难度 考察点
5. 最长回文子串 中等 要求字符连续，可用中心扩展 $O(n^2)$ 且空间 $O(1)$
132. 分割回文串 II 困难 状态建在前缀上求最少切割数，回文表只作预处理
647. 回文子串 中等 统计回文子串数量而非求最值，区间只需布尔判定
1143. 最长公共子序列 中等 双串前缀 DP，与本题的等价桥梁：s 对 reverse(s) 求 LCS
1312. 让字符串成为回文串的最少插入次数 困难 同一张区间表求最小代价，答案为 n 减本题结果
LCR 094. 分割回文串 II 困难 132 的同题换皮，检验回文预处理与前缀 DP 的衔接