专题进阶 · 动态规划推荐总顺序 · 第 72 / 148 课

按区间长度填表,枚举最后一次合并位置,理解重复区间子问题。

先学会这些,再进入本课 二维 DP 递归与调用栈
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

区间 DPInterval DP

按区间长度推进,枚举分割点或最后一步,把小区间合成大区间。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

按区间长度填表,枚举最后一次合并位置,理解重复区间子问题。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

矩阵 A 为 10×30,B 为 30×5,C 为 5×60;乘积 ABC 相同,但加括号的位置会改变多少乘法次数?

02一步步得到方法

最后一步把一个区间分成两段

矩阵乘法结合律保证结果相同,但计算成本不同。定义 dp[l][r] 为计算矩阵 l..r 乘积的最少标量乘法次数。只有一个矩阵无需相乘,成本为 0。

最后一次乘法在 k 与 k+1 之间划分:先算 l..k,再算 k+1..r,最后将两个结果相乘。若维度数组为 p,最后成本为 p[l]·p[k+1]·p[r+1]。枚举所有 k,取总成本最小。

计算顺序由依赖长度决定

每个候选只依赖更短区间,因此按长度 2、3、…填表,而不是随意按 l,r 升序。边界 l,r 是完整状态,只记录长度不够,因为不同位置的矩阵维度不同。

本方法强调最优子结构:固定最后分割后,两侧若不是各自最优,就能替换成更便宜计算,降低总成本。它不要求贪心地先乘当前最便宜的一对。

按长度填表是在遵守依赖

当前区间的每个切分点都会产生更短子区间,因此先算长度1,再算长度2直到全长,可以保证读取的状态已经就绪。按左端点单独递增不一定满足右侧子区间依赖。

切分代价不只是两个子问题最优值之和,还可能包含把两部分合起来的额外成本。矩阵链乘法的外侧维度决定这一项,写错维度即使 DP 顺序正确也会得到错误答案。

03把一个小例子完全算清楚

p=[10,30,5,60]。

步骤计算与状态为什么这样做
长度 2:AB10×30×5=1500结果维度 10×5
长度 2:BC30×5×60=9000结果维度 30×60
先 AB 后 C1500+10×5×60=4500分割 k=1
先 BC 后 A9000+10×30×60=27000取较小 4500

窄屏可左右滑动表格,阅读完整计算与理由。

同样三个矩阵,合法顺序的成本差了六倍。

04为什么这个方法成立

  1. 长度 1 成本为 0,基础正确。
  2. 最后一次乘法必有某个分割 k,枚举覆盖全部括号结构。
  3. 两段使用已求出的最优解,取最小即为当前区间最优。

05把推导翻译成代码

Python · 可独立运行的教学实现

def matrix_chain(p):
    n = len(p)-1
    if n <= 0:
        return 0
    dp = [[0]*n for _ in range(n)]
    for length in range(2,n+1):
        for left in range(n-length+1):
            right = left+length-1
            dp[left][right] = min(
                dp[left][k]+dp[k+1][right]+p[left]*p[k+1]*p[right+1]
                for k in range(left,right))
    return dp[0][n-1]

逐个理解关键决定

range(2,n+1)
先短后长,保证所有子区间已计算。
p[k+1]
分割两侧相乘的内维度,不是 p[k]。

06时间、空间与实现范围

O(n²) 个区间,每个 O(n) 分割,时间 O(n³),空间 O(n²)。

输出最佳括号结构还需保存最优 k。某些特殊区间 DP 可优化,但需要额外性质,不能一概降低到平方。

07改变条件,检查哪里会出错

先乘局部成本最小的一对必全局最优

这缺乏通用贪心保证,局部结果维度会改变后续巨大成本。

把所有区间问题都套成相同 O(n³)

要分别计算状态数、每个状态候选数,以及转移是否可用前缀和或其他性质加速。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

两个矩阵 2×3 和 3×4 成本?

需要一点提示

没有选择分割的自由。

查看解析与答案

2×3×4=24。

练习 2 · 边界与辨析

为什么 dp[l][r] 不能只由 dp[l+1][r] 得到?

需要一点提示

最后分割可能在中间任何位置。

查看解析与答案

只去掉一端会漏掉一般括号结构,必须枚举全部合法 k。

练习 3 · 变式与迁移

合并石堆也是区间 DP 吗?

需要一点提示

最后一次合并的左右部分。

查看解析与答案

若只允许相邻合并,可按区间枚举分割;合并代价通常由区间和给出,常配合前缀和。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。