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:AB | 10×30×5=1500 | 结果维度 10×5 |
| 长度 2:BC | 30×5×60=9000 | 结果维度 30×60 |
| 先 AB 后 C | 1500+10×5×60=4500 | 分割 k=1 |
| 先 BC 后 A | 9000+10×30×60=27000 | 取较小 4500 |
窄屏可左右滑动表格,阅读完整计算与理由。
同样三个矩阵,合法顺序的成本差了六倍。
04为什么这个方法成立
- 长度 1 成本为 0,基础正确。
- 最后一次乘法必有某个分割 k,枚举覆盖全部括号结构。
- 两段使用已求出的最优解,取最小即为当前区间最优。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
两个矩阵 2×3 和 3×4 成本?
需要一点提示
没有选择分割的自由。
查看解析与答案
2×3×4=24。
为什么 dp[l][r] 不能只由 dp[l+1][r] 得到?
需要一点提示
最后分割可能在中间任何位置。
查看解析与答案
只去掉一端会漏掉一般括号结构,必须枚举全部合法 k。
合并石堆也是区间 DP 吗?
需要一点提示
最后一次合并的左右部分。
查看解析与答案
若只允许相邻合并,可按区间枚举分割;合并代价通常由区间和给出,常配合前缀和。