跳至主要內容

矩阵连乘

路九阳大约 17 分钟教学文档算法设计与分析动态规划区间动态规划最优子结构Python

矩阵连乘

中等 区间动态规划 Python

同样计算三个矩阵的乘积,为什么一种加括号方式需要27000次标量乘法,另一种只需4500次?

本节学习目标

  • 会建模: 用矩阵链的左右端点定义最小成本状态,从最后一次相乘推导转移。
  • 会追踪: 按区间长度填表,比较全部合法切分点,再恢复一种最优括号方案。
  • 会核对: 检查维度下标、单矩阵边界、候选成本与寻找最优计划的复杂度。

前置知识:矩阵乘法的维度规则、二维列表与循环;可先阅读打家劫舍理解状态与转移。

题目描述

给定按固定顺序相乘的 n≥1n\geq1 个矩阵 A1,A2,…,AnA_1,A_2,\ldots,A_n,相邻矩阵的维度保证可乘。只通过改变括号调整计算先后,求最少的标量乘法次数,并给出一种达到最小成本的完全加括号方案。

这里采用普通矩阵乘法的成本模型:一个 a×ba\times b 的矩阵与一个 b×cb\times c 的矩阵相乘,结果大小为 a×ca\times c,需要 abcabc 次标量乘法。只统计乘法次数,不统计标量加法,也不采用其他矩阵乘法算法的成本公式。

参数、输出与编号规则

  • 输入维度列表 p,长度为 n+1n+1,每个值必须为正整数;第 ii 个矩阵大小为 pi−1×pip_{i-1}\times p_i。
  • 矩阵编号从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)

对应 A1:10×30A_1:10\times30、A2:30×5A_2:30\times5、A3:5×60A_3:5\times60:

括号方案第一次相乘最后一次相乘总成本
(A1A2)A3(A_1A_2)A_310×30×5=150010\times30\times5=150010×5×60=300010\times5\times60=30004500
A1(A2A3)A_1(A_2A_3)30×5×60=900030\times5\times60=900010×30×60=1800010\times30\times60=1800027000

结果维度都是 10×6010\times60,计算成本却不同。示例中的 A1A2 表示矩阵相乘;编号连写用于展示括号,不表示把矩阵名拼接成一个新变量。

题目分析

核心结论

枚举最后一次相乘的切分点k:先得到左链和右链的最优结果,再加上这两个结果相乘的成本。按区间长度从短到长计算,使每次转移依赖的状态都已求出。

从最后一次相乘确定子问题

任意一种完全加括号的方案,最后一步一定是把两个连续矩阵链的乘积相乘:

(Ai⋯Ak)(Ak+1⋯Aj),i≤k<j. (A_i\cdots A_k)(A_{k+1}\cdots A_j),\qquad i\leq k<j.

左侧结果大小为 pi−1×pkp_{i-1}\times p_k,右侧结果大小为 pk×pjp_k\times p_j。无论两侧内部如何加括号,结果维度都不变,因此最后一次相乘的成本固定为:

pi−1pkpj. p_{i-1}p_kp_j.

这说明当前问题可以由两个更短的区间子问题得到,但必须比较所有合法的 kk,不能任意选一个中点就认定最优。

定义状态、边界与转移

定义 dp[i][j]:按原顺序计算 Ai⋯AjA_i\cdots A_j 的最少标量乘法次数。

单个矩阵不需要乘法:

dp[i][i]=0. dp[i][i]=0.

对于 i<ji<j:

dp[i][j]=min⁡i≤k<j{dp[i][k]+dp[k+1][j]+pi−1pkpj}. dp[i][j]=\min_{i\leq k<j} \left\{dp[i][k]+dp[k+1][j]+p_{i-1}p_kp_j\right\}.

每个候选成本由三部分组成:左侧内部的最优成本、右侧内部的最优成本、最后一次相乘的成本。不能只比较最后一项,也不能把矩阵个数当作乘法成本。

split[i][j] 保存取得最小值时的 kk。单矩阵没有切分点,使用 None 表示。候选相等时不覆盖已有记录,而 kk 从小到大枚举,因此实现遵守题目中的相等处理约定。

为什么可以使用两侧的最优值

固定最后一次相乘的切分点后,若某一侧没有采用最优方案,就可以把它换成同一矩阵链的更优方案:结果维度不变,与另一侧相乘仍然合法,总成本只会降低。

所以最优整体方案的两侧也可以采用对应区间的最优值。反过来,每个合法切分点下,两侧的最优方案加上最后一次相乘,都构成当前区间的一种合法方案。

枚举所有切分点就覆盖了全部可能的最后一步,取其中最小值便得到当前区间最优解。配合单矩阵边界,可按区间长度归纳证明整个算法正确。

按区间长度计算,而不是重复递归

长度为 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开始。

长度1与长度2:建立可复用结果

输入为 p = [10, 30, 5, 60]。先令 dp[1][1]、dp[2][2]、dp[3][3] 都为0,再计算:

当前区间唯一切分点候选成本保存的成本与切分点
[1, 2]10 + 0 + 10 * 30 * 5 = 1500dp[1][2] = 1500,split[1][2] = 1
[2, 3]20 + 0 + 30 * 5 * 60 = 9000dp[2][3] = 9000,split[2][3] = 2

长度3:比较整体区间的两个候选

切分点 kk左链成本右链成本最后一次相乘总成本是否更新当前最优
10900010×30×60=1800010\times30\times60=1800027000是,第一个候选
21500010×5×60=300010\times5\times60=30004500是,比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不能用过小的固定上界初始化最小值

复杂度分析

先看结论

设矩阵数为 nn,维度列表长度为 n+1n+1。按整数乘法、加法、比较与下标访问为单位成本;若维度很大,实际整数运算还需要考虑位数成本。

任务时间复杂度辅助空间复杂度说明
求最优成本与切分表O(n3)O(n^3)O(n2)O(n^2)每个有效区间只计算一次
根据已有表恢复一种方案O(n+B)O(n+B)O(n+B)O(n+B)BB 为方案字符串的实际字符数,计入符号列表与结果字符串,不含已有表
完整求解,包含方案恢复O(n3)O(n^3)O(n2)O(n^2)对 n≥1n\geq1,方案生成不改变总体上界

若把一个矩阵标号视为一个输出符号,括号方案有 O(n)O(n) 个符号;若计入 A10 等标号中的数字字符,则 B=O(nlog⁡(n+1))B=O(n\log(n+1))。代码先收集片段再一次拼接,避免反复拼接越来越长的中间字符串。

时间复杂度

有效区间数为 n(n+1)/2n(n+1)/2。长度为 LL 的区间有 n−L+1n-L+1 个,每个区间需要比较 L−1L-1 个切分点,因此候选成本计算总次数为:

∑L=2n(n−L+1)(L−1)=n3−n6. \sum_{L=2}^{n}(n-L+1)(L-1)=\frac{n^3-n}{6}.

加上表初始化等开销,总时间为 O(n3)O(n^3)。单矩阵不进入候选循环,处理为常数时间。

示例中的4500是最优方案执行时的标量乘法次数;O(n3)O(n^3) 是寻找最优方案的运行时间,二者的任务与计数对象不同。没有读取缓存的普通递归可能反复求解同一区间,不能直接使用这里的复杂度结论。

辅助空间复杂度

dp 与 split 分别使用 (n+1)×(n+1)(n+1)\times(n+1) 的二维表,合计 O(n2)O(n^2) 空间。填表本身用循环完成,没有递归栈。

恢复括号时显式栈最坏有 O(n)O(n) 个任务,片段与结果字符串占用 O(n+B)O(n+B) 空间。与两张表合计,总辅助空间仍为 O(n2)O(n^2);输入维度列表的存储单独计为 O(n)O(n)。

易错点

易错点正确理解
将维度列表长度当成矩阵数量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] 表示一个 8×48\times4 的矩阵,成本为0,方案为 A1,对角线切分点为 None。[8] 不足以表示一个矩阵,主实现抛出 ValueError。

2. 对维度 [10, 20, 30],两个矩阵相乘的成本与结果维度分别是多少?

参考答案

成本为 10×20×30=600010\times20\times30=6000 次标量乘法,结果为 10×3010\times30。结果元素个数是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))。最后一次相乘成本为 5×3×5=755\times3\times5=75,总成本为 150+180+75=405150+180+75=405。

4. 三个矩阵均为 5×55\times5 时,为什么本文输出 (A1(A2A3))?另一个括号方案是否错误?

参考答案

两种方案都需要 125+125=250125+125=250 次乘法,都正确。本文从小到大枚举切分点,只在严格更小时更新,因此整体保留 k=1k=1,恢复为 (A1(A2A3))。

进阶思考

5. 有4个矩阵时,有多少个有效区间、多少个非平凡区间、多少次候选成本计算?为什么这些数量不同?

参考答案

有效区间10个,其中4个为单矩阵,非平凡区间6个。候选成本计算为 3×1+2×2+1×3=103\times1+2\times2+1\times3=10 次。

状态数量统计区间;候选次数还要计入每个区间的切分点数量。二维状态数量不能直接作为时间复杂度。

6. 若不保存切分表,只保存成本表,是否还能恢复一种最优方案?如果需要输出全部最优方案,能否直接沿用本文的恢复开销?

参考答案

可以在恢复某个区间时重新枚举切分点,寻找满足最优成本等式的一个切分点;保存切分表则能直接读取,省去再次搜索。

输出全部最优方案需要保存或重新寻找所有并列最优切分,并组合左右方案。最优方案数量可能很大,例如所有矩阵同维度时所有括号方式都同样最优,不能直接沿用仅恢复一种方案的输出成本。

继续学习: 与打家劫舍比较前缀状态,再阅读最大子数组和比较线性动态规划与分治摘要;课堂串联见2026年秋第6次课。

上次编辑于:
贡献者: zlzhou,molittle