最长回文子序列如何用区间 DP 求解？和回文子串有什么区别？

简化版

最长回文子序列用区间 DP，dp[i][j] 表示 s[i..j] 内最长回文子序列长度。若 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2；否则取 max(dp[i+1][j], dp[i][j-1])。

详细版

回文子序列不要求连续，所以不能用中心扩展直接解决。状态按区间两端字符是否相等来讨论：两端相等时，它们可以作为同一个回文子序列的首尾；两端不等时，最优答案必然来自去掉左端或去掉右端。

初始化单个字符区间 dp[i][i]=1。因为 dp[i][j] 依赖 i+1，所以 i 要从大到小遍历，j 从 i+1 到 n-1。时间和空间复杂度都是 O(n^2)。

完整版教学

一、子序列和子串的区别

子串必须连续，子序列可以跳过字符。

s = "bbbab"
最长回文子序列："bbbb"，长度 4
它不是连续子串，因为中间跳过了 a

因此最长回文子串常用中心扩展或 Manacher，而最长回文子序列更适合区间 DP。

二、状态为什么定义成区间

回文天然由两端向中间收缩。定义：

dp[i][j]：字符串 s[i..j] 中最长回文子序列长度

这个状态能表达“两端是否一起选”的决策，也能复用更短区间的结果。

记忆钩子：只要问题围绕左右端点取舍，优先想到区间 DP。

三、两端相等时的转移

如果 s[i] == s[j]，两端字符可以作为回文的首尾：

dp[i][j] = dp[i+1][j-1] + 2

例如 "bbb" 的两端都是 b，中间 "b" 的最长回文子序列长度为 1，所以整体为 3。

四、两端不等时的转移

如果 s[i] != s[j]，两端不可能同时作为同一个回文子序列的首尾。最优答案来自：

去掉左端：dp[i+1][j]
去掉右端：dp[i][j-1]

取较大值：

dp[i][j] = max(dp[i+1][j], dp[i][j-1])

五、遍历顺序为什么是 i 倒序

dp[i][j] 依赖 dp[i+1][j-1] 和 dp[i+1][j]，也就是更大的 i。所以外层 i 要从 n-1 到 0。

i 从下往上
j 从左往右
确保下方和左下方状态已经算好

二维表中可以理解为从短区间逐渐扩展到长区间。

六、代码模板

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];
}

如果要输出具体子序列，需要额外记录选择路径或从 dp 表反推。

七、常见误区与追问

误区：把子序列当成子串。 子序列可以不连续，中心扩展不能直接求最长回文子序列。
误区：遍历顺序写成 i 正序。 依赖的 dp[i+1][j] 尚未计算，会读到错误状态。
误区：两端相等时还取 max。 对长度而言，两端相等可以直接接内部最优加 2。
追问：复杂度是多少？ 状态数量 O(n^2)，每个状态 O(1) 转移。
追问：和 LCS 有什么关系？ 它等价于 s 和 reverse(s) 的最长公共子序列长度。
追问：能空间优化吗？ 可以压成一维，但需要小心保存左下角 dp[i+1][j-1]。

八、加强记忆

最长回文子序列要记住“区间两端做选择”：两端相同，就把它们包住内部答案；两端不同，就丢左或丢右取最大。它不是子串题，所以不要求连续；它是区间 DP，所以遍历顺序必须保证内部和下方状态先算好。用 "bbbab" 能很好地区分子序列和子串，也能解释为什么答案可以跳过中间字符。

简化版

详细版