跳转至

第 103 章　区间 DP

本章配套 1 道例题，见 §例题。 前置：DP 入门、线性 DP

线性动态规划沿一维序列推进，区间动态规划换了推进的载体：沿区间长度从小到大推进。 状态是一个区间 \([l, r]\)，「最后一步」是最后一次合并的断点 \(k\)。

\(O(n^3)\) 的三重循环在 Python 里是硬伤，所以本章的重点之一是 把最内层的断点枚举下沉到 C 层——维护一张转置表，用 map 一次算完所有断点。

同源的另外三种形态：树形 DP 沿子树推进、状压 DP 沿集合推进、 DAG 上的 DP 沿拓扑序推进。

计数版本：把 \(\min\)/\(\max\) 换成 \(+\) 就是计数 DP，取模的时机与陷阱见 DP 入门 · 计数 DP 与取模。

状态是一个区间 \([l, r]\)，转移枚举最后一次合并的断点。

\[f[l][r] = \min_{l \le k < r}\big(f[l][k] + f[k+1][r]\big) + \text{cost}(l, r)\]

1　枚举顺序必须按区间长度

\(f[l][r]\) 依赖的 \(f[l][k]\) 和 \(f[k+1][r]\) 都是更短的区间。所以外层必须枚举长度：

# [片段]
for length in range(2, n + 1):        # 区间长度从小到大：短区间先算好，长区间才敢用
    for l in range(1, n - length + 2):    # 左端点上界由「右端点不越过 n」倒推而来
        r = l + length - 1            # 长度为 length 的区间是 [l, r]，闭区间
        for k in range(l, r):         # 断点 k 取到 r-1：切成 [l,k] 与 [k+1,r] 两段非空
            ...

写成 for l: for r: 的双层循环也可以，但必须 \(l\) 倒序、\(r\) 正序， 否则依赖没算好。按长度枚举更不容易错，推荐固定用这个写法。

2　环形区间：破环成链

若区间首尾相连（如「石子摆成一圈」），标准做法是把数组复制一倍变成长度 \(2n\) 的链， 再在所有长度为 \(n\) 的区间里取最优。

BISHI145 是链不是环，不需要复制。读题时要确认这一点。

3　例题 · BISHI145 石子合并（较难）

题号 题名 难度 题解
BISHI145 石子合并 较难 题解

\(N\) 堆石子排成一排，每次合并相邻两堆、代价为两堆之和，求最小总代价。\(N \le 300\)。

\[f[l][r] = \min_{l \le k < r}\big(f[l][k] + f[k+1][r]\big) + (m_l + \cdots + m_r)\]

最后那一项与断点 \(k\) 无关——无论怎么合，最后一次合并的代价一定是整段之和。 用前缀和 \(O(1)\) 取出。

复杂度：状态 \(O(N^2) = 9\times10^4\)，每个状态枚举 \(O(N)\) 个断点 ⇒ \(O(N^3) \approx 4.5\times10^6\)。

4　Python 关键：维护转置表把内层下沉 C 层

最内层的「枚举断点取 min」是 \(4.5\times10^6\) 次 Python 迭代，勉强能过但很险。 可以整段下沉，但需要同时维护一张转置表：

要取的数据 在 f 里 是否连续
\(f[l][k]\)，\(k = l..r-1\) f[l][l:r] —— 第 \(l\) 行的一段 ✅ 连续
\(f[k+1][r]\)，\(k = l..r-1\) 第 \(r\) 列的一段 ❌ 不连续

所以额外维护 fT[r][k+1] = f[k+1][r]，于是：

# [片段]
from operator import add

# f[l][l:r] 依次是 f[l][k]，k = l..r-1；fT[r][l+1:r+1] 依次是 f[k+1][r]，同一批 k
# map(add, ...) 逐位相加得到全部断点的候选值，min 一次取最小，两步都在 C 层
best = min(map(add, f[l][l:r], fT[r][l + 1:r + 1]))

map(add, ...) 把两个切片逐元素相加、min 取最小，全在 C 层。 每次更新 f[l][r] 时同步写一份 fT[r][l]。

代价是双倍内存和一次额外写入，换来内层循环从 Python 层挪到 C 层。 \(N = 300\) 时这个改写把耗时从约 3 秒降到 0.2 秒量级。

题解：solutions/nowcoder/BISHI145/sol.py（已通过官方样例验证）

5　区间 DP 的其它经典模型

问题 状态与转移
括号匹配的最长合法子串 \(f[l][r]\)，匹配则 \(f[l+1][r-1]+2\)，否则枚举断点
回文划分（最少切几刀） \(f[i] = \min\{f[j] + 1\}\)，\(s[j+1..i]\) 是回文
矩阵链乘 \(f[l][r] = \min f[l][k] + f[k+1][r] + p_{l-1}p_k p_r\)
能量项链（环形） 破环成链

6　本章速查

形态 状态载体 枚举顺序 「最后一步」是什么
区间 DP 区间 \([l,r]\) 按长度从小到大 最后一次合并的断点 \(k\)
Python 关键 做法
区间 DP 内层下沉 维护转置表 fT，用 min(map(add, f[l][l:r], fT[r][l+1:r+1]))
规模判据 Python
区间 DP \(O(n^3)\) \(n \le 300\) ✅（内层下沉后）、\(n \le 500\) ⚠️

树形 / 状压 / DAG 三种形态的速查条目在各自章末。