区间 DP

2026-06-02

状态 dp[i][j] 是一段区间的最优答案,转移枚举区间内的”分割点” k。关键不是公式,而是枚举顺序: 必须从短区间到长区间,因为 dp[i][j] 要先有 dp[i][k] 和 dp[k+1][j] 才算得出来。记住这一句,石子合并、戳气球、矩阵链乘就是同一道题。

直觉 — 区间状态 + 分割点 + 枚举顺序

线性 DP 的状态是”一个点”(dp[i]),区间 DP 的状态是”一段区间”(dp[i][j])。当问题问的是”对一段连续的东西做某种合并/切分/匹配的最优代价”,几乎就是它。

转移的标准动作: 在 [i, j] 里枚举一个分割点 k,把大区间劈成两半,递归调用两个子区间的答案。

cost(i, k, j) 是”把两半拼起来”那一步的代价,题目自定义。石子合并里它是 sum(a[i..j]),矩阵链乘里它是 p[i-1] * p[k] * p[j],戳气球里它是 nums[i-1] * nums[k] * nums[j+1]。

枚举顺序: 为什么必须按长度

dp[i][j] 依赖 dp[i][k] 和 dp[k+1][j],两个子区间长度都 严格小于 [i, j]。所以填表必须保证算 dp[i][j] 时,所有更短的区间都已算完。

三种合法写法,效果等价:

写法 外层 内层 备注
按长度(推荐) len 从 2 到 n 左端点 i,j = i+len-1 最直观,不容易写错
i 倒序 + j 正序 i 从 n-1 到 0 j 从 i+1 到 n-1 利用了”依赖项 i 更大、j 更小”的性质
记忆化递归 — — 不用想顺序,递归自然保证拓扑序

错误写法: i 正序 + j 正序 — 算 dp[0][n-1] 时,dp[1][n-1](同样依赖项)还没算。

动画 — 石子合并填表过程

数组 [3, 1, 5, 2],求把所有石子合并成一堆的最小总代价 (每次合并相邻两堆,代价 = 两堆之和)。

下面的动画严格按”长度从小到大”的顺序填 dp 表。点”下一步”,看三件事:

  1. 当前填的格子(蓝边) 是哪个区间 dp[i][j]。
  2. 黄色高亮的格子 是这一步参考的两个子区间 dp[i][k] 和 dp[k+1][j] — 它们一定在当前格子的左下方,因为长度更短、已经填完。
  3. 最终的 dp[0][3] 就是答案。

填表方向永远是”短区间已就位 → 长区间从它们组装出来”,这就是区间 DP 的全部物理图像。

模板 — Python (按长度从小到大循环)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def interval_dp(a):
    n = len(a)
    dp = [[0] * n for _ in range(n)]      # dp[i][i] = 0 (单元素无操作代价)
    prefix = [0]                          # 区间和常用前缀和加速
    for x in a:
        prefix.append(prefix[-1] + x)

    for length in range(2, n + 1):        # 1. 区间长度: 从短到长
        for i in range(n - length + 1):   # 2. 左端点 i
            j = i + length - 1            # 3. 右端点 j
            dp[i][j] = float('inf')
            for k in range(i, j):         # 4. 分割点 k,把 [i,j] 拆成 [i,k] + [k+1,j]
                cost = prefix[j+1] - prefix[i]   # 题目自定义 (这里是石子合并)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost)
    return dp[0][n-1]

四层循环骨架: len → i → (j 由 len 和 i 推出) → k,时间复杂度 ,空间 。这套骨架几乎所有区间 DP 都不变,变的只有 cost 那一行。

记忆化递归版:

1
2
3
4
5
6
from functools import cache

@cache
def solve(i, j):
    if i == j: return 0
    return min(solve(i, k) + solve(k+1, j) + cost(i, k, j) for k in range(i, j))

代码更短,且不用纠结枚举顺序。代价: 递归栈深 ,n 上千要改迭代。

三道范式 — 石子合并 / 戳气球 / 矩阵链乘

三道题用的都是上面那个模板,只有 cost 不一样。把这三个 cost 背下来,半数区间 DP 题就归约完了。

1. 石子合并 — cost = sum(a[i..j])

LC 1000。最后一次合并把 [i,k] 和 [k+1,j] 两堆合起来,代价 = 两堆石头总数 = prefix[j+1] - prefix[i](不论 k 在哪儿都一样,所以可以提到 k 循环外面)。

2. 戳气球 — 反向定义,dp[i][j] = 开区间 (i, j) 内全戳完的最大收益

LC 312。直觉陷阱: 正向想”先戳哪个” — 戳完后左右气球变相邻,状态污染了相邻关系,子问题不再独立。

正难则反: 枚举区间 (i, j) 内 最后戳的那个气球 k。最后戳 k 的那一刻,(i, k) 和 (k, j) 里的气球都已被戳光,k 的左邻就是 i、右邻就是 j,收益 nums[i] * nums[k] * nums[j] 完全确定。

1
2
3
# 在 nums 两端各加一个 1,变成 [1, ...原数组..., 1]
dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
               for k in range(i+1, j))

注意分割点这里写的是 dp[i][k] + dp[k][j] (k 自己被排除在两个子区间之外,因为 k 是 最后 戳的)。

3. 矩阵链乘 — cost = p[i-1] * p[k] * p[j]

经典的”加括号”问题。矩阵 的维度是 ,dp[i][j] = 计算 的最小标量乘法次数。

最后一次乘法把 [i..k] 的结果 和 [k+1..j] 的结果 相乘,代价 p[i-1] * p[k] * p[j]。

1
2
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]
               for k in range(i, j))

跟石子合并几乎是一个模子,只是 cost 换了形状。

记忆法 / 易错点

一句口诀: 状态是区间,转移找分点,枚举从短到长。

四件容易翻车的小事:

  1. dp[i][i] 的初值: 单元素区间的最优值。求和型(石子合并) 0;求积型(戳气球) 0;计数/匹配型(回文子序列) 1。题目说什么就写什么,不要照搬模板。
  2. 分割点的范围: k in range(i, j) 表示 [i,k] 和 [k+1,j] 都非空; 戳气球那种”k 是最后操作”的写法用 range(i+1, j),因为 k 自己不属于子区间。哪种取决于你对 dp 的定义,别混。
  3. 边界扩展: 戳气球、合并端点型问题,常在原数组首尾各加一个哨兵(1 或 0),让分割点的”左右邻居”永远有意义,省一大堆 if。
  4. i 正序 + j 正序的陷阱: 看似自然,实际错的。要么按长度,要么 i 倒序 j 正序,要么记忆化。搞不清就用记忆化递归,稳。

判题口诀:

  • 区间合并/切分 / 最优加括号 / 回文匹配 / “区间最后一步是 …” → 区间 DP
  • 三层循环跑得动 → n 一般 ≤ 500
  • 跑不动了 → 找四边形不等式优化到 ,或换思路

LeetCode 练习

热身(回文/对称型): 5. 最长回文子串 · 516. 最长回文子序列 · 647. 回文子串

进阶(合并/反向枚举型): 312. 戳气球 · 1000. 合并石头的最低成本 · 664. 奇怪的打印机 · 546. 移除盒子 · 87. 扰乱字符串

刷到第三题,你会发现这些题的差别只在 cost 函数的形状,骨架完全是模板那四层循环。区间 DP 就这么回事。