516. 最长回文子序列

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 2.2k 阅读时长 ≈ 7 分钟

考点

  • 区间DP
  • 回文序列

思路

1. 问题描述

给定一个字符串 \(s\)，求其中 最长回文子序列 的长度。

  • 子序列（subsequence）：从原串中删除若干字符（可以为 0 个），剩余字符的相对顺序保持不变。例如，字符串 "abcde" 的子序列可以是 "ace"。
  • 回文串（palindrome）：正着读和反着读完全相同，例如 "aba"、"abba"。

本题要求的是：在所有可能的子序列中，找出一个长度最大的回文子序列，并返回其长度。

例如：

  • 输入："bbbab"
    • 最长回文子序列可以是 "bbbb"，长度为 4
  • 输入："cbbd"
    • 最长回文子序列是 "bb"，长度为 2

2. 为什么使用动态规划

朴素枚举所有子序列的数目是 \(2^n\) 级别，很快就无法承受。 然而，回文子序列具有明显的 “从两端向中间收缩” 的结构：

  • 如果两端相等，可以尝试把两端都选入回文；
  • 如果两端不等，可以考虑舍弃一端，转而在较小的子区间中寻找答案。

这种“区间逐渐缩小”的过程非常适合用 区间动态规划（interval DP） 来建模。

3. 区间 DP 的建模：状态设计

3.1 状态定义

在本题中，最自然的区间定义是： \[ f[l][r] = \text{在子串 } s[l..r] \text{ 中，最长回文子序列的长度} \] 这里采用 1-based 记法更便于和代码对应：

  • 代码中的字符串下标是 0..n-1；
  • DP 中的区间下标是 l, r ∈ [1, n]；
  • 两者之间的关系为：
    • 区间端点 \(l, r\) 对应的字符是 s[l-1] 和 s[r-1]。

最终答案是整个串上的结果： \[ \text{Answer} = f[1][n] \]

3.2 基本思路

对于任意区间 \([l, r]\)（\(l \le r\)），只需根据 区间两端的字符关系 来讨论：

  1. 若 s[l-1] == s[r-1]
    • 两端可以同时取进回文子序列；
    • 中间剩余部分是区间 \([l+1, r-1]\)；
    • 回文长度增加 2，与中间的最优结果相加。
  2. 若 s[l-1] != s[r-1]
    • 无法让两端同时作为同一个回文的“首尾”；
    • 最长回文子序列要么完全在 \([l+1, r]\)，要么完全在 \([l, r-1]\)；
    • 取两者的较大值即可。

4. 状态转移推导

4.1 情况一：两端字符相等

若 \(s[l-1] = s[r-1]\)，则可以把这两个字符都加入某个回文子序列的两端： \[ f[l][r] = f[l+1][r-1] + 2 \] 解释：

  • 区间 \([l+1, r-1]\) 中的最长回文子序列长度为 \(f[l+1][r-1]\)；
  • 再在左右两端各加一个同样字符，形成更长的回文串；
  • 总长度增加 2。

需要注意的是：

  • 当 \(l+1 > r-1\)（例如长度为 2 的区间，使得中间为空区间）时，可以认为 \(f[l+1][r-1] = 0\)，即空区间中最长回文子序列长度为 0。

4.2 情况二：两端字符不相等

若 \(s[l-1] \neq s[r-1]\)，两端不能同时作为同一个回文的“首尾”，最长回文子序列只能完全来自以下两种情况之一：

  1. 舍弃左端字符，只在区间 \([l+1, r]\) 中寻找；
  2. 舍弃右端字符，只在区间 \([l, r-1]\) 中寻找。

因此： \[ f[l][r] = \max(f[l+1][r], f[l][r-1]) \] 这就是本题区间 DP 的完整转移逻辑。

5. 边界条件（Base Case）

当区间只包含一个字符时，显然该子串的最长回文子序列长度为 1： \[ \forall i \in [1, n], \quad f[i][i] = 1 \] 对于空区间，可以认为： \[ f[l][r] = 0 \quad \text{当 } l > r \] 在代码中通常不显式存储空区间的 DP 值，而是通过数组默认初始化为 0 来间接实现。

6. 计算顺序：为什么要按长度/按起点顺序枚举

区间 DP 的核心约束是：

当计算 \(f[l][r]\) 时，它依赖的状态（例如 \(f[l+1][r]\)、\(f[l][r-1]\)、\(f[l+1][r-1]\)）必须已经被计算出来。

观察本题的转移：

  • 无论哪种情况，\(f[l][r]\) 依赖的都是 区间更短 的状态。
  • 因此，只要保证“先算所有短区间，再算长区间”，就能保证依赖有序。

常见的两种计算顺序如下。

7. 实现一：按区间长度从小到大枚举

7.1 循环结构说明

外层枚举区间长度 len：

  • len = 1 时：区间 [i, i]，直接设为 1；
  • len = 2..n 时：依次计算所有长度为 len 的区间。

内层枚举左端点 l：

  • 右端点 r = l + len - 1；
  • 需要保证 r <= n，因此循环条件为 l + len - 1 <= n。

当 len >= 2 时：

  • 如果 s[l-1] == s[r-1]，使用 \(f[l][r] = f[l+1][r-1] + 2\)；
  • 否则使用 \(f[l][r] = \max(f[l+1][r], f[l][r-1])\)。

7.2 带注释代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    static const int maxn = 1e3 + 5;

    int longestPalindromeSubseq(string s) {
        // f[l][r] 表示区间 s[l..r]（1-based）中最长回文子序列的长度
        int f[maxn][maxn] = {}; // 全部初始化为 0，用于处理空区间的情况
        int n = s.size();

        // 长度为 1 的区间，显然最长回文子序列长度为 1
        for (int i = 1; i <= n; ++i)
            f[i][i] = 1;

        // 枚举区间长度 len = 2..n
        for (int len = 2; len <= n; ++len) {
            // 枚举左端点 l，右端点 r = l + len - 1 不能超过 n
            for (int l = 1; l + len - 1 <= n; ++l) {
                int r = l + len - 1;
                if (s[l - 1] == s[r - 1]) {
                    // 两端字符相等，可以作为回文的首尾
                    // 中间子区间是 [l+1, r-1]，长度 f[l+1][r-1]，再加上两端的 2 个字符
                    f[l][r] = f[l + 1][r - 1] + 2;
                } else {
                    // 两端字符不等，只能舍弃一端
                    // 要么来自 [l+1, r]，要么来自 [l, r-1]
                    f[l][r] = max(f[l + 1][r], f[l][r - 1]);
                }
            }
        }

        // 整个串 s[1..n] 的最长回文子序列长度
        return f[1][n];
    }
};

这一版本结构清晰，完整体现了“先短后长的区间 DP 模板”：

  • 外层：len 从小到大；
  • 内层：枚举所有起点 l，根据区间长度确定 r。

8. 实现二：按左端点从右到左、右端点从左到右枚举

除了按“区间长度”枚举之外，只要保证：

每次计算 \(f[i][j]\) 时，其依赖状态已经被计算完毕，

就可以改变循环顺序。

观察本题的依赖：

  • \(f[i][j]\) 依赖 \(f[i+1][j]\)、\(f[i][j-1]\)、\(f[i+1][j-1]\)。

只要确保：

  • i 从大到小（这样 i+1 始终在“后面”已算过），
  • j 从小到大（这样 j-1 在“前面”已算过），

依赖关系也能满足。

8.1 循环结构说明

  • 外层：i 从 n 递减到 1；
  • 内层：j 从 i+1 增加到 n。

在进入内层循环之前，先给 f[i][i] 赋值为 1，表示长度为 1 的区间。

8.2 带注释代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    static const int maxn = 1e3 + 5;

    int longestPalindromeSubseq(string s) {
        // f[i][j] 表示区间 s[i..j]（1-based）中最长回文子序列的长度
        int f[maxn][maxn] = {}; // 初始化为 0，便于处理空区间
        int n = s.size();

        // i 从 n 递减到 1
        for (int i = n; i >= 1; --i) {
            // 区间 [i, i]，只有一个字符，本身就是回文
            f[i][i] = 1;
            // j 从 i+1 到 n，保证 i < j，区间长度至少为 2
            for (int j = i + 1; j <= n; ++j) {
                if (s[i - 1] == s[j - 1]) {
                    // 两端字符相等，可以作为回文首尾
                    // 中间区间为 [i+1, j-1]，长度 f[i+1][j-1]
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    // 两端字符不等，只能舍弃一端
                    f[i][j] = max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }

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

可以验证：在这套循环顺序下，使用到的依赖项：

  • f[i+1][j]：因为 i 从大到小，所以 i+1 的行已经算过；
  • f[i][j-1]：因为 j 从小到大，所以 j-1 的列已经算过；
  • f[i+1][j-1]：同理，在 i+1 那一行、j-1 那一列时已经被计算。

因此，此实现同样符合区间 DP 的依赖拓扑顺序。

9. 两种写法的对比与总结

9.1 共同点

  • 状态定义完全一致：\(f[l][r]\) 或 \(f[i][j]\) 都表示子串上的最长回文子序列长度；

  • 状态转移完全相同：根据两端字符是否相等选择不同公式；

  • 边界条件一致：单个字符区间长度为 1 的回文；

  • 时间复杂度、空间复杂度相同： \[ \text{时间复杂度} = O(n^2), \quad \text{空间复杂度} = O(n^2) \]

9.2 不同点

  • 第一种写法体现了 区间长度层层扩展 的思想，模板感强，适合作为“区间 DP 入门模板”；
  • 第二种写法利用了 下标的遍历方向 来隐式保证依赖顺序，代码略短，更接近常见的 0-based 区间 DP 写法。