区间动态规划：最长回文子序列与通用模板

1. 前言：区间 DP 的战略地位与核心逻辑

在高级算法面试中，区间动态规划（Interval Dynamic Programming）往往被视为区分中高级候选人的「分水岭」。它不仅考察代码实现，更考察候选人对子问题依赖关系的深刻理解。区间 DP 专门用于解决那些涉及「连续子区间」合并或划分的问题，其核心逻辑在于由内向外、由短及长地构建最优解。

为何初学者难以直观定义区间 DP？ 初学者的思维往往局限于线性增长（如 i → i+1）。然而，区间问题要求我们同时维护左端点 i 和右端点 j。最难突破的障碍是计算顺序的依赖性：大区间 [i, j] 的最优解通常依赖于其内部小区间（如 [i+1, j-1]）的结果。如果按照常规的双重循环顺序遍历，极易在计算当前状态时引用尚未初始化的「未来状态」。

本报告将通过深度拆解最长回文子序列（LPS）及其变体，揭示区间 DP 的通用建模范式。

2. 核心题目详解：LeetCode 516. 最长回文子序列 (LPS)

2.1 题目原型与深度剖析

题目要求： 给定一个字符串 s，找出其中最长的回文子序列的长度。

约束： n ≤ 1000，暗示 O(n²) 的时间复杂度是可接受的，而 O(2ⁿ) 的暴力搜索必将超时。

核心辨析：子序列 vs. 子串

• 子串 (Substring)： 必须连续。如 "cbbd" 的最长回文子串是 "bb"。
• 子序列 (Subsequence)： 可以不连续，只需保持相对顺序。例如 "cbbd" 的子序列包括 "cbd"、"bb" 等。
• 面试逻辑点： 子序列赋予了我们「跳过」某些字符的权利，这种非连续性正是区间 DP 状态转移中 max(dp[i+1][j], dp[i][j-1]) 的来源。

示例 1： s = "bbbab"，输出 4。回文子序列可以是 "bbbb"。

示例 2： s = "cbbd"，输出 2。回文子序列是 "bb"。即使两个 'b' 在原串中相邻，我们也应视其为选择了下标 1 和 2 的字符。若输入为 "abcba"，即便去掉中间的 'c'，两端的 'a' 和 'b' 依然能构成回文。

2.2 解题思路：从对称性观察到动态规划

1. 状态定义： 定义 dp[i][j] 为字符串 s 在区间 [i, j] 内的最长回文子序列长度。最终答案即为 dp[0][n-1]。

2. 核心决策逻辑（为什么想到区间 DP？）： 观察区间的两端字符 s[i] 和 s[j]：

• 若 s[i] == s[j]： 这两个字符可以匹配，作为回文的最外层。长度在内部区间 [i+1, j-1] 的基础上加 2。
  • 方程：dp[i][j] = dp[i+1][j-1] + 2
• 若 s[i] ≠ s[j]： 说明这两个字符无法同时出现在同一个最长回文子序列中。我们需要在「舍弃 s[i]」和「舍弃 s[j]」之间取最优解。
  • 方程：dp[i][j] = max(dp[i+1][j], dp[i][j-1])

3. 可视化填表过程（以 "bbbab" 为例）： 关键在于计算顺序。由于 dp[i][j] 依赖于下一行 i+1 的数据，我们必须倒着遍历 i（从 n-1 到 0）。

i \ j	0 (b)	1 (b)	2 (b)	3 (a)	4 (b)
0 (b)	1	2	3	3	4
1 (b)	-	1	2	2	3
2 (b)	-	-	1	1	3
3 (a)	-	-	-	1	1
4 (b)	-	-	-	-	1

注：dp[2][4] 对应串 "bab"，因为 s[2]==s[4]，故 dp[2][4] = dp[3][3] + 2 = 1 + 2 = 3。

2.3 工业级代码实现与避坑指南

Python 实现

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1  # 基础子问题：单个字符
        for j in range(i + 1, n):
            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]

C++ 实现 (更体现内存布局)

int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        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];
}

避坑指南（The Pitfalls）：

1. 遍历方向错误： 如果写成 for i in range(n)，在计算 dp[0][5] 时，dp[1][4] 尚未被更新（仍为初始值 0），导致结果全错。
2. 空间溢出： 1000 × 1000 的 int 矩阵约占用 4MB 内存，但在一些嵌入式或严格限制内存的笔试中，需考虑下文提到的空间优化。

3. 扩展进阶：LeetCode 1039. 多边形三角剖分的最低得分

3.1 几何问题的区间化转换

该题要求将 N 边形剖分为 N-2 个三角形，使顶点权值乘积之和最小。

核心策略： 固定一边 (i, j)，并在中间寻找一个顶点 k。在这个模型中，边 (i, j) 一定是某个三角形 (i, k, j) 的底边。一旦选定了 k，原来的多边形就被切割成了三部分：

1. 中间的三角形 (i, k, j)。
2. 左侧的子多边形（顶点为 i … k）。
3. 右侧的子多边形（顶点为 k … j）。

3.2 状态转移方程

定义 v 为顶点权重数组。dp[i][j] 为顶点 i 到 j 组成的多边形剖分后的最低得分。

dp[i][j] = min_{i < k < j} { dp[i][k] + dp[k][j] + v[i] × v[k] × v[j] }

此处的「底边固定」思想，成功将复杂的几何嵌套转化为了区间的线性分割。

4. 方法论沉淀：区间 DP 通用模板与实战套路

4.1 万能解题模板

为了避免遍历顺序出错，工业界最稳健的写法是按区间长度升序遍历。这样能百分之百保证在计算长区间时，短区间（子问题）已经完成计算。

# 通用模板：三层循环
for length in range(2, n + 1):           # 1. 遍历区间长度
    for i in range(n - length + 1):      # 2. 遍历左端点
        j = i + length - 1               # 3. 计算右端点
        for k in range(i + 1, j):        # 4. 遍历中间分割点/决策点
            dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k][j] + cost)

4.2 「举一反三」题单推荐

1. LC 1312. 最少插入次数： 求让字符串成为回文的最少步数。逻辑：n - LPS(s)。
2. LC 1547. 切棍子的最小成本： 典型的「切割点即分割点」问题。
3. LC 3472. K 次操作后的 LPS： 区间 DP 的进阶，状态需增加一个维度 dp[i][j][k]。

5. 面试实战：高频追问与应对策略

问：如何将空间复杂度从 O(n²) 优化到 O(n)？

答： 观察 LPS 转移方程，dp[i][j] 只依赖于 dp[i+1]（下一行）和 dp[i]（当前行）。我们可以使用滚动数组。进一步观察，如果使用一行数组 dp[j]，dp[i+1][j-1] 会被上一轮的值覆盖，因此需要一个变量 pre 记录左下角的值：

new_dp[j] = (s[i] == s[j]) ? pre + 2 : max(dp[j], dp[j-1])

问：求回文「子串」与「子序列」的 DP 定义有何不同？

答： 子串要求连续，其 dp[i][j] 通常是布尔值，表示 [i, j] 是否为回文。若 s[i] ≠ s[j]，dp[i][j] 直接为 false，不存在 max 转移，因为断开了就不是子串了。

问：递归加记忆化 vs. 递推（自底向上）？

答： 记忆化搜索（自顶向下）更容易思考，且能自动剪枝（只访问合法状态）；递推则在空间优化上更具优势，且在 C++/Java 中由于消除了函数调用开销，执行速度通常更快。

结语： 区间 DP 的本质是处理「边界的扩张与收缩」。掌握了 i, j 两个指针的摆动规律，就拿到了通往高级动态规划大门的钥匙。算法能力的建立没有捷径：做完 1000 道，再来 1000 道。