矩阵连乘
矩阵连乘
中等 区间动态规划 Python同样计算三个矩阵的乘积,为什么一种加括号方式需要27000次标量乘法,另一种只需4500次?
本节学习目标
- 会建模: 用矩阵链的左右端点定义最小成本状态,从最后一次相乘推导转移。
- 会追踪: 按区间长度填表,比较全部合法切分点,再恢复一种最优括号方案。
- 会核对: 检查维度下标、单矩阵边界、候选成本与寻找最优计划的复杂度。
前置知识:矩阵乘法的维度规则、二维列表与循环;可先阅读打家劫舍理解状态与转移。
题目描述
给定按固定顺序相乘的 个矩阵 ,相邻矩阵的维度保证可乘。只通过改变括号调整计算先后,求最少的标量乘法次数,并给出一种达到最小成本的完全加括号方案。
这里采用普通矩阵乘法的成本模型:一个 的矩阵与一个 的矩阵相乘,结果大小为 ,需要 次标量乘法。只统计乘法次数,不统计标量加法,也不采用其他矩阵乘法算法的成本公式。
参数、输出与编号规则
- 输入维度列表
p,长度为 ,每个值必须为正整数;第 个矩阵大小为 。 - 矩阵编号从1开始,维度列表下标从0开始。例如
p = [10, 30, 5, 60]表示3个矩阵,而不是4个矩阵。 - 保持矩阵顺序,不得排序或交换矩阵。只需输入维度,不需要输入矩阵元素,也不实际完成矩阵乘法。
- 计算成本表
dp与切分表split,并由它们输出最少乘法次数及一种最优括号方案。 dp[i][j]与split[i][j]使用矩阵闭区间[i, j];第0行、第0列仅用于让下标与矩阵编号对齐。- 单个矩阵的成本为0,括号方案为其自身。若有多种最优方案,本文保留当前区间中最小的最优切分点。
输入至少包含一个矩阵。主实现对长度不足2、非整数或非正维度抛出 ValueError,不会把空矩阵链当作单矩阵处理。程序不修改输入列表。
贯穿示例
输入维度: [10, 30, 5, 60]
最少标量乘法次数: 4500
一种最优括号方案: ((A1A2)A3)
对应 、、:
| 括号方案 | 第一次相乘 | 最后一次相乘 | 总成本 |
|---|---|---|---|
| 4500 | |||
| 27000 |
结果维度都是 ,计算成本却不同。示例中的 A1A2 表示矩阵相乘;编号连写用于展示括号,不表示把矩阵名拼接成一个新变量。
题目分析
核心结论
枚举最后一次相乘的切分点k:先得到左链和右链的最优结果,再加上这两个结果相乘的成本。按区间长度从短到长计算,使每次转移依赖的状态都已求出。
从最后一次相乘确定子问题
任意一种完全加括号的方案,最后一步一定是把两个连续矩阵链的乘积相乘:
左侧结果大小为 ,右侧结果大小为 。无论两侧内部如何加括号,结果维度都不变,因此最后一次相乘的成本固定为:
这说明当前问题可以由两个更短的区间子问题得到,但必须比较所有合法的 ,不能任意选一个中点就认定最优。
定义状态、边界与转移
定义 dp[i][j]:按原顺序计算 的最少标量乘法次数。
单个矩阵不需要乘法:
对于 :
每个候选成本由三部分组成:左侧内部的最优成本、右侧内部的最优成本、最后一次相乘的成本。不能只比较最后一项,也不能把矩阵个数当作乘法成本。
split[i][j] 保存取得最小值时的 。单矩阵没有切分点,使用 None 表示。候选相等时不覆盖已有记录,而 从小到大枚举,因此实现遵守题目中的相等处理约定。
为什么可以使用两侧的最优值
固定最后一次相乘的切分点后,若某一侧没有采用最优方案,就可以把它换成同一矩阵链的更优方案:结果维度不变,与另一侧相乘仍然合法,总成本只会降低。
所以最优整体方案的两侧也可以采用对应区间的最优值。反过来,每个合法切分点下,两侧的最优方案加上最后一次相乘,都构成当前区间的一种合法方案。
枚举所有切分点就覆盖了全部可能的最后一步,取其中最小值便得到当前区间最优解。配合单矩阵边界,可按区间长度归纳证明整个算法正确。
按区间长度计算,而不是重复递归
长度为 length 的区间 [i, j] 满足 j = i + length - 1。其依赖的 [i, k] 与 [k + 1, j] 都比当前区间短,因此按以下顺序计算:
长度1:初始化对角线为0
长度2:计算相邻两个矩阵的成本
长度3:利用更短区间,比较两个切分点
……
长度n:得到完整矩阵链的最优成本
如果直接按行随意更新,可能读到还没求出的更短区间。若采用递归,也必须先查询缓存才能避免重复计算;仅仅把结果写入二维表,并不能保证每个状态只求一次。
根据切分表恢复括号
恢复区间 [i, j] 时,单矩阵直接输出 Ai;否则读取 k = split[i][j],输出左括号、左侧方案、右侧方案与右括号。
本文用显式栈完成这一遍历,避免恢复括号时依赖 Python 递归深度。栈后进先出,因此按“右括号、右侧任务、左侧任务、左括号”的顺序压入,弹出时就是需要的输出顺序。
恢复只选择表中记录的一种方案,不枚举全部最优括号方式。
实现代码
Python 区间动态规划与括号恢复
matrix_chain(p) 返回成本表和切分表;build_order(split, i, j) 在已计算的有效区间内恢复一种最优方案。以下程序可以独立运行,并打印主示例的成本、方案与两张表。
def matrix_chain(p):
"""返回矩阵链的最优成本表与切分表,矩阵编号从1开始。"""
if len(p) < 2 or any(type(x) is not int or x <= 0 for x in p):
raise ValueError("维度列表至少包含两个正整数")
n = len(p) - 1
dp = [[0] * (n + 1) for _ in range(n + 1)]
split = [[None] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
best = None
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
if best is None or cost < best:
best = cost
split[i][j] = k
dp[i][j] = best
return dp, split
def build_order(split, i, j):
"""根据已求出的切分表,恢复闭区间 [i, j] 的一种最优括号方案。"""
parts = []
stack = [(i, j)]
while stack:
task = stack.pop()
if isinstance(task, str):
parts.append(task)
continue
left, right = task
if left == right:
parts.append(f"A{left}")
else:
k = split[left][right]
stack.extend([")", (k + 1, right), (left, k), "("])
return "".join(parts)
if __name__ == "__main__":
p = [10, 30, 5, 60]
n = len(p) - 1
dp, split = matrix_chain(p)
print("最少乘法次数:", dp[1][n])
print("最优括号方案:", build_order(split, 1, n))
print("成本表 dp:")
for i in range(1, n + 1):
print(" ".join("-" if j < i else str(dp[i][j])
for j in range(1, n + 1)))
print("切分表 split:")
for i in range(1, n + 1):
print(" ".join("-" if split[i][j] is None else str(split[i][j])
for j in range(1, n + 1)))
for dims in ([10, 20], [10, 30, 5], [5, 5, 5, 5]):
costs, cuts = matrix_chain(dims)
count = len(dims) - 1
print(f"{dims} -> {costs[1][count]}, {build_order(cuts, 1, count)}")
输出:
最少乘法次数: 4500
最优括号方案: ((A1A2)A3)
成本表 dp:
0 1500 4500
- 0 9000
- - 0
切分表 split:
- 1 2
- - 2
- - -
[10, 20] -> 0, A1
[10, 30, 5] -> 1500, (A1A2)
[5, 5, 5, 5] -> 250, (A1(A2A3))
成本表中 - 表示不使用的下三角区间;切分表中 - 还包括没有切分点的对角线。代码虽然将整个 dp 初始化为0,但转移只读取已经计算好的有效区间,不能把任意未计算单元的0当作合法成本。
best = None 表示尚未检查候选,第一次候选会直接成为当前最优值。这样不需要猜测一个足够大的固定常量,也避免最优成本超过该常量时无法正确更新。
算法执行过程
观察任务
| 阶段 | 观察任务 |
|---|---|
| 填表前 | 将维度列表转换为每个矩阵的行列数,区分维度数与矩阵数 |
| 计算中 | 按长度定位区间,写出每个切分点的三项成本 |
| 得到最优值后 | 核对切分点记录,按切分表恢复括号 |
| 检查边界 | 用单矩阵核对0,用相等成本核对保留最小切分点的约定 |
交互动画
动画默认维度为 [10, 30, 5, 60],与正文一致,表示3个矩阵。矩阵编号及成本表、切分表的行列编号从1开始;维度下标从0开始,第i个矩阵大小为 p[i - 1] × p[i]。
点击“下一步”或“自动播放”,观察按区间长度从短到长填表。蓝色表示正在计算的区间,橙色与紫色分别标出当前切分点依赖的左链、右链成本;计算面板将候选成本拆成“左链内部+右链内部+最后一次相乘”。问号表示尚未计算,下三角为空白;成本表对角线为0,切分表对角线的横线表示没有切分点。
动画会在每个候选检查后显示当前最优值,直到该区间的所有切分点检查完毕才是最终值。Python 主实现则在区间候选循环结束后写入成本表,两者的依赖顺序、最终成本及切分点一致。相等候选不覆盖先前结果,保留最小的最优切分点。
支持上一步、下一步、自动播放、暂停、重来、预设切换和全屏。自定义输入为2到9个正整数,表示1到8个矩阵,每个维度限1到10000,用逗号或空格分隔;这些显示限制也保证浏览器中的整数成本能精确计算,不是正文 Python 的维度上限。空输入、零、负数或小数会提示修改,保留当前演示。
主示例完成后得到最小成本4500及方案 ((A1A2)A3)。可切换单矩阵检查成本0,切换相等维度核对保留切分点的约定,或用四矩阵示例核对成本405。方案由切分表恢复,不实际执行矩阵乘法;动画另存步骤快照用于回放,其存储开销不等同于正文算法的辅助空间。
长度1与长度2:建立可复用结果
输入为 p = [10, 30, 5, 60]。先令 dp[1][1]、dp[2][2]、dp[3][3] 都为0,再计算:
| 当前区间 | 唯一切分点 | 候选成本 | 保存的成本与切分点 |
|---|---|---|---|
[1, 2] | 1 | 0 + 0 + 10 * 30 * 5 = 1500 | dp[1][2] = 1500,split[1][2] = 1 |
[2, 3] | 2 | 0 + 0 + 30 * 5 * 60 = 9000 | dp[2][3] = 9000,split[2][3] = 2 |
长度3:比较整体区间的两个候选
| 切分点 | 左链成本 | 右链成本 | 最后一次相乘 | 总成本 | 是否更新当前最优 |
|---|---|---|---|---|---|
| 1 | 0 | 9000 | 27000 | 是,第一个候选 | |
| 2 | 1500 | 0 | 4500 | 是,比27000更小 |
最终保存 dp[1][3] = 4500、split[1][3] = 2。整个示例共计算4个候选成本:两个长度2区间各1次,长度3区间2次;不是只计算最终区间的两个候选。
从切分点恢复一种最优方案
区间 [1, 3],切分点2 → 左侧 [1, 2],右侧 [3, 3]
左侧 [1, 2],切分点1 → 左侧 A1,右侧 A2 → (A1A2)
右侧 [3, 3] → A3
整体方案 → ((A1A2)A3)
恢复阶段不再尝试其他切分点,也不重新计算最优成本。它读取的是求最优值时记录的决策。
单矩阵、相等候选与较大成本
| 维度列表 | 正确结果 | 核对重点 |
|---|---|---|
[10, 20] | 成本0,方案 A1 | 单矩阵不需要相乘 |
[5, 5, 5, 5] | 成本250,方案 (A1(A2A3)) | 两种括号成本相同,整体保留切分点1 |
[1000, 1000, 1000] | 成本1000000000 | 不能用过小的固定上界初始化最小值 |
复杂度分析
先看结论
设矩阵数为 ,维度列表长度为 。按整数乘法、加法、比较与下标访问为单位成本;若维度很大,实际整数运算还需要考虑位数成本。
| 任务 | 时间复杂度 | 辅助空间复杂度 | 说明 |
|---|---|---|---|
| 求最优成本与切分表 | 每个有效区间只计算一次 | ||
| 根据已有表恢复一种方案 | 为方案字符串的实际字符数,计入符号列表与结果字符串,不含已有表 | ||
| 完整求解,包含方案恢复 | 对 ,方案生成不改变总体上界 |
若把一个矩阵标号视为一个输出符号,括号方案有 个符号;若计入 A10 等标号中的数字字符,则 。代码先收集片段再一次拼接,避免反复拼接越来越长的中间字符串。
时间复杂度
有效区间数为 。长度为 的区间有 个,每个区间需要比较 个切分点,因此候选成本计算总次数为:
加上表初始化等开销,总时间为 。单矩阵不进入候选循环,处理为常数时间。
示例中的4500是最优方案执行时的标量乘法次数; 是寻找最优方案的运行时间,二者的任务与计数对象不同。没有读取缓存的普通递归可能反复求解同一区间,不能直接使用这里的复杂度结论。
辅助空间复杂度
dp 与 split 分别使用 的二维表,合计 空间。填表本身用循环完成,没有递归栈。
恢复括号时显式栈最坏有 个任务,片段与结果字符串占用 空间。与两张表合计,总辅助空间仍为 ;输入维度列表的存储单独计为 。
易错点
| 易错点 | 正确理解 |
|---|---|
| 将维度列表长度当成矩阵数量 | n = len(p) - 1,一个矩阵需要两个维度 |
| 为了减少成本改变矩阵顺序 | 本题只允许改变括号,不能排序或交换矩阵 |
| 将单矩阵成本设为其元素个数 | 单矩阵无须乘法,dp[i][i] = 0 |
| 只比较最后一次相乘的成本 | 要加上左右子链的最优内部成本 |
写成 p[i] * p[k] * p[j] | 左链的行数是 p[i - 1],对应一开始的矩阵行数 |
| 让切分点等于j | 右子链会为空,合法范围是 i <= k < j |
| 随意按行填表 | 应按区间长度递增,先完成所有被依赖的短区间 |
| 写入dp就认为已经记忆化 | 递归还必须查询缓存;本文用自底向上确保每个状态只求一次 |
| 用固定的有限常量代表无穷大 | 最优成本可能超过它,本文用 None 表示尚无候选 |
| 只算最优值,却忘记记录切分点 | 若要恢复方案,应同步保存 split[i][j] |
| 认为二维表意味着平方级时间 | 每个区间还要枚举切分点,总时间为三次方级 |
课堂练习
先独立作答,再逐题展开答案核对。
基础核对
1. p = [8, 4] 表示几个矩阵?最优成本、方案和切分点分别是什么?p = [8] 是否符合题意?
参考答案
[8, 4] 表示一个 的矩阵,成本为0,方案为 A1,对角线切分点为 None。[8] 不足以表示一个矩阵,主实现抛出 ValueError。
2. 对维度 [10, 20, 30],两个矩阵相乘的成本与结果维度分别是多少?
参考答案
成本为 次标量乘法,结果为 。结果元素个数是300,不能把它当作乘法次数。
过程推演
3. 对 [5, 10, 3, 12, 5],先写出长度2、3的状态,再比较完整区间的全部切分点,给出最优方案。
参考答案
长度2:dp[1][2] = 150、dp[2][3] = 360、dp[3][4] = 180。
长度3:dp[1][3] = 330、dp[2][4] = 330。
完整区间三个候选为580、405、630,最小值为405,整体切分点为2,方案为 ((A1A2)(A3A4))。最后一次相乘成本为 ,总成本为 。
4. 三个矩阵均为 时,为什么本文输出 (A1(A2A3))?另一个括号方案是否错误?
参考答案
两种方案都需要 次乘法,都正确。本文从小到大枚举切分点,只在严格更小时更新,因此整体保留 ,恢复为 (A1(A2A3))。
进阶思考
5. 有4个矩阵时,有多少个有效区间、多少个非平凡区间、多少次候选成本计算?为什么这些数量不同?
参考答案
有效区间10个,其中4个为单矩阵,非平凡区间6个。候选成本计算为 次。
状态数量统计区间;候选次数还要计入每个区间的切分点数量。二维状态数量不能直接作为时间复杂度。
6. 若不保存切分表,只保存成本表,是否还能恢复一种最优方案?如果需要输出全部最优方案,能否直接沿用本文的恢复开销?
参考答案
可以在恢复某个区间时重新枚举切分点,寻找满足最优成本等式的一个切分点;保存切分表则能直接读取,省去再次搜索。
输出全部最优方案需要保存或重新寻找所有并列最优切分,并组合左右方案。最优方案数量可能很大,例如所有矩阵同维度时所有括号方式都同样最优,不能直接沿用仅恢复一种方案的输出成本。
继续学习: 与打家劫舍比较前缀状态,再阅读最大子数组和比较线性动态规划与分治摘要;课堂串联见2026年秋第6次课。
