算法►动态规划

区间 DP：从「区间划分」理解最优子结构

区间 DP 的本质是：在一个连续区间内枚举“最后一次决策点”，把区间拆分成若干更小区间，通过最优子结构组合得到整体最优解。它解决的是“前缀 DP 无法表达的、区间内相互依赖的问题”。

一、为什么需要区间 DP（与线性 DP 的根本区别）

线性 DP 在解决什么问题？

  • 状态通常是：前 i 个元素
  • 决策是：当前位置选 or 不选
  • 子问题天然是前缀 / 后缀

例如：

  • LIS
  • LCS
  • 背包
  • 股票状态机

哪些问题线性 DP 无法直接建模？

当问题满足以下特征之一时，几乎必然是区间 DP：

  • 决策发生在区间内部，而不是边界
  • 子问题不是“前 i 个”，而是“任意子区间”
  • 当前最优解依赖于区间被切成两段或多段

这时就必须显式引入「区间左右端点」。

二、区间 DP 的标准状态定义

区间 DP 的统一模板：

1
dp[i][j] 表示：区间 [i, j] 内的最优解

常见的隐含约束：

  • i <= j
  • 区间长度逐渐变大
  • 转移依赖更小的区间

三、经典入门：516 最长回文子序列

状态定义

1
dp[i][j]：字符串 s 在区间 [i, j] 内的最长回文子序列长度

边界条件

  • i > j：空区间 → 0
  • i == j：单字符 → 1

状态转移

  • 如果 s[i] == s[j]：
1
dp[i][j] = dp[i+1][j-1] + 2
  • 如果 s[i] != s[j]：
1
dp[i][j] = max(dp[i+1][j], dp[i][j-1])

遍历顺序（区间 DP 的“坑点”）

dp[i][j] 依赖：

  • dp[i+1][j]
  • dp[i][j-1]
  • dp[i+1][j-1] 对于 i 来说是后面的状态，对于 j 来说是前面的状态

因此：

  • i 必须从大到小
  • j 必须从小到大
1
2
for i = n-1 .. 0:
    for j = i .. n-1:

常见易错点

  • 区分「子序列」与「子串」：一个可以不连续，一个必须连续

四、区间切分模型：1039 多边形三角剖分

抽象模型

这类问题的统一抽象是：

在区间 (i, j) 中，枚举一个“最后参与决策的点 k”

状态定义

1
dp[i][j]：由顶点 i 到 j 构成的多边形的最低三角剖分得分

状态转移（「枚举中点」为例）

1
2
3
4
dp[i][j] = min over k ∈ (i, j):
    dp[i][k] +
    values[i] * values[k] * values[j] +
    dp[k][j]

其中：

  • (i, k) 和 (k, j) 是两个子多边形
  • (i, k, j) 是当前枚举的三角形

这是区间 DP 最典型的结构，与回文问题完全不同，但模型统一。

本质理解

  • 固定一条边 (i, j)
  • 枚举“与这条边形成三角形的顶点 k”
  • 将问题拆成左右两个区间

五、极值对抗模型：375 猜数字大小 II

为什么它也是区间 DP？

因为：

  • 每次选择一个 k
  • 会把区间 [l, r] 分成：
    • [l, k-1]
    • [k+1, r]

状态定义

1
dp[l][r]：在区间 [l, r] 内保证猜中所需的最少现金

状态转移（min + max 的组合）

1
2
dp[l][r] = min over k ∈ [l, r]:
    k + max(dp[l][k-1], dp[k+1][r])

为什么是 max？

  • 因为要保证“最坏情况下也能赢”
  • 属于 对抗型 / 博弈型区间 DP

六、区间 DP 的统一分类总结

类型 特点 代表题
双端收缩 操作在区间两端 516
枚举区间每一个顶点 枚举分割点 k 1039
对抗博弈 min + max 375

七、区间 DP 的工程级思维模型

建模四步法

  1. 区间 [i, j] 表示什么？
  2. 决策发生在区间的哪里？
  3. 子区间如何划分？
  4. 边界区间是什么？

遍历顺序的通用规律

  • 区间长度从小到大
  • 或等价地：
    • i 从大到小
    • j 从小到大

谁正谁反，取决于你依赖的是 i+1 还是 j-1。

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。