数据结构与算法 / 系统课时

枚举分割点合并区间答案

枚举分割点合并区间答案

有些区间问题不能只看左右端点,而要尝试“从哪里切开”。区间 DP 的核心做法是枚举所有合法分割点,把左右子区间的已知答案与本次合并代价组合成候选值,再从候选中选出最优解。

学习目标

  • 能写出 [l, r] 在分割点 k 处拆成两个子区间的通用结构。
  • 能正确确定 k 的枚举范围,避免空区间和越界。
  • 能把左右子问题答案与合并代价组合,并比较全部候选结果。

分割点转移的本质

设 dp[l][r] 表示闭区间 [l, r] 的最优答案。若在 k 后切开,左右两部分分别是 [l, k] 和 [k+1, r]。只要这两个子区间都比原区间短,就可以先求它们,再合并。

一个常见的最小化结构是:

dp[l][r]=minl<=k<r(dp[l][k]+dp[k+1][r]+cost(l,k,r))dp[l][r] = min_{l <= k < r}(dp[l][k] + dp[k+1][r] + cost(l,k,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]。下面程序同时记录最佳分割点,便于验证选择结果。

python
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))

预期输出

text
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。

共有 O(n2)O(n^2) 个区间,每个区间最多枚举 O(n)O(n) 个分割点,因此时间复杂度为 O(n3)O(n^3),空间复杂度为 O(n2)O(n^2)。当题目具有“区间可拆成左右两段,整体答案由两段答案与一次合并代价决定”的结构时,分割点枚举通常就是最直接的建模方式。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

枚举分割点合并区间答案

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通