数据结构与算法 / 系统课时
枚举分割点合并区间答案
枚举分割点合并区间答案
有些区间问题不能只看左右端点,而要尝试“从哪里切开”。区间 DP 的核心做法是枚举所有合法分割点,把左右子区间的已知答案与本次合并代价组合成候选值,再从候选中选出最优解。
学习目标
- 能写出
[l, r]在分割点k处拆成两个子区间的通用结构。 - 能正确确定
k的枚举范围,避免空区间和越界。 - 能把左右子问题答案与合并代价组合,并比较全部候选结果。
分割点转移的本质
设 dp[l][r] 表示闭区间 [l, r] 的最优答案。若在 k 后切开,左右两部分分别是 [l, k] 和 [k+1, r]。只要这两个子区间都比原区间短,就可以先求它们,再合并。
一个常见的最小化结构是:
其中 cost(l,k,r) 代表把左右两个已经求好的子结果合并时新增的代价。不同题目的差异通常集中在这个合并代价,以及最终取最小值、最大值还是计数和。

枚举范围决定正确性
对于非空的左右两段,k 必须满足 l <= k < r。如果让 k == r,右区间会变成 [r+1, r];如果从 l+1 才开始,又会漏掉“左边只有一个元素”的合法切分。
因为父区间依赖两个更短区间,外层仍然要按区间长度递增。长度为 1 时通常没有切分点,直接使用初始化值;从长度 2 开始才进入 k 的枚举。
主示例:矩阵链乘法
矩阵链乘法是分割型区间 DP 的经典模型。若矩阵维度由 dims 表示,则矩阵 A1 的尺寸是 dims[0] × dims[1],A2 是 dims[1] × dims[2]。状态 dp[l][r] 表示把第 l 到第 r 个矩阵相乘所需的最少标量乘法次数。
当分割点为 k 时,新增合并代价是 dims[l] * dims[k + 1] * dims[r + 1]。下面程序同时记录最佳分割点,便于验证选择结果。
def matrix_chain_order(dims):
n = len(dims) - 1
if n <= 0:
return 0, []
dp = [[0] * n for _ in range(n)]
split = [[-1] * n for _ in range(n)]
for length in range(2, n + 1):
for l in range(0, n - length + 1):
r = l + length - 1
best = float("inf")
# k 后切开:左边 [l, k],右边 [k+1, r]。
for k in range(l, r):
merge_cost = dims[l] * dims[k + 1] * dims[r + 1]
candidate = dp[l][k] + dp[k + 1][r] + merge_cost
if candidate < best:
best = candidate
split[l][r] = k
dp[l][r] = best
return dp[0][n - 1], split
def build_order(split, l, r):
if l == r:
return f"A{l + 1}"
k = split[l][r]
left = build_order(split, l, k)
right = build_order(split, k + 1, r)
return f"({left}×{right})"
if __name__ == "__main__":
dims = [10, 30, 5, 60]
cost, split = matrix_chain_order(dims)
print(cost)
print(build_order(split, 0, len(dims) - 2))预期输出
4500
((A1×A2)×A3)用候选值验证转移
对 dims = [10, 30, 5, 60],总区间包含三个矩阵,因此顶层只有两个分割点。若 k = 0,先算 A2×A3,子区间代价为 9000,再把 A1 合并进去需要 18000,总计 27000。
若 k = 1,先算 A1×A2,代价是 1500,再与 A3 合并需要 3000,总计 4500。程序枚举两个候选后选择 4500,所以输出与手算一致。用一个小输入逐个展开候选,是检查分割式转移最有效的方法之一。
常见错误与复杂度
分割型区间 DP 常见错误有三类:把 k 枚举到 r 导致空右区间;合并代价的下标少加或多加 1;以及只计算一个看似合理的分割点,没有比较所有候选。矩阵链乘法中特别要区分“矩阵编号”和“维度数组编号”,后者比矩阵数量多 1。
共有 个区间,每个区间最多枚举 个分割点,因此时间复杂度为 ,空间复杂度为 。当题目具有“区间可拆成左右两段,整体答案由两段答案与一次合并代价决定”的结构时,分割点枚举通常就是最直接的建模方式。