区间动态规划

◎

本节目标

把连续区间的最优解按长度递增地组织起来。

识别信号

对象是连续子数组或子串，答案由更短的连续区间组合而来；常见关键词是合并、分割或最后一次操作。

状态定义与转移推导

令 dp[l][r] 表示闭区间 [l,r] 的答案。合法性题先判断两端与内部；分割题枚举 k；最后决策题把最后操作的元素留在区间边界之间。

初始化与遍历顺序

长度为一的区间先初始化，再按长度从小到大枚举，确保转移读到的子区间已经完成。

通用模板

for length = 2 .. n:
  for left = 0 .. n - length:
    right = left + length - 1
    for split in [left, right): update dp[left][right]

空间优化与复杂度

二维状态通常需要 O(n²) 空间，枚举分割点为 O(n³)；不要在没有结构依据时强行压缩。

母题序列

1. 最长回文子串（必学）：合法性区间，也可比较中心扩展。
2. 石子合并（必学）：枚举最后一次合并的分割点。
3. 戳气球（拓展）：枚举区间中最后被戳的气球。

常见误区

把长度顺序写反、忘记前缀和的闭区间边界，或把“最后操作”误写成“第一步操作”。

迁移方向

当状态不再是连续区间而是树的子树时转向树形 DP；当决策集合可用位表示时转向状态压缩。