矩阵链乘法

概述

矩阵链乘法问题是动态规划的经典范例：给定 $n$ 个矩阵的链，求完全括号化方案使标量乘法次数最少。该问题展示了最优子结构的典型应用——最优括号化在某个位置分裂后，左右两段也必须是最优括号化的。

定义

矩阵链乘法问题（Matrix-Chain Multiplication）

输入：矩阵链 $A_1,A_2,\dots ,A_n$，其中 $A_i$ 的维度为 $p_{i-1}\times p_i$。

输出：一个完全括号化方案，使得计算矩阵链乘积所需的标量乘法次数最少。

设 $m[i,j]$ 为计算 $A_i{A}_{i+1}\cdots A_j$ 所需的最少标量乘法次数，则： $m[i,j]=\{\begin{array}{ll}0& \text{若 }i=j\\ \underset{i\le k<j}{\min }\{m[i,k]+m[k+1,j]+p_{i-1}\cdot p_k\cdot p_j\}& \text{若 }i<j\end{array}$

其中 $p_{i-1}\cdot p_k\cdot p_j$ 是在位置 $k$ 分裂后，将两个子结果矩阵相乘的代价。

核心性质

1. 最优子结构

设 $A_i\cdots A_j$ 的最优括号化在 $A_k$ 和 $A_{k+1}$ 之间分裂。则子链 $A_i\cdots A_k$ 的括号化方案必须是计算该子链的最优方案，$A_{k+1}\cdots A_j$ 同理。

证明（反证法）：若 $A_i\cdots A_k$ 存在代价更小的括号化方案，将其替换到原方案中，可得到 $A_i\cdots A_j$ 的代价更小的括号化方案——与最优性矛盾。

2. 自底向上计算

MATRIX-CHAIN-ORDER(p):
    n = p.length - 1
    let m[1..n, 1..n] and s[1..n-1, 2..n] be new tables
    for i = 1 to n:
        m[i,i] = 0
    for l = 2 to n:                    // l 为链长度
        for i = 1 to n - l + 1:
            j = i + l - 1
            m[i,j] = ∞
            for k = i to j - 1:
                q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]
                if q < m[i,j]:
                    m[i,j] = q
                    s[i,j] = k        // 记录最优分裂点
    return m and s

3. 构造最优解

通过 $s$ 表递归构造最优括号化方案：

PRINT-OPTIMAL-PARENS(s, i, j):
    if i == j:
        print "A" + i
    else:
        print "("
        PRINT-OPTIMAL-PARENS(s, i, s[i,j])
        PRINT-OPTIMAL-PARENS(s, s[i,j]+1, j)
        print ")"

4. 子问题总数与计算顺序

• 子问题总数：$\left(\genfrac{}{}{0ex}{}{n}{2}\right)+n=O(n^2)$ 个（即所有满足 $1\le i\le j\le n$ 的 $(i,j)$ 对）
• 每个子问题需要遍历 $O(n)$ 个分裂点
• 总时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$（$m$ 表和 $s$ 表各占 $O(n^2)$）

5. 计算顺序示例

对于 $n=4$ 个矩阵，计算顺序按链长度递增：

1. 长度 2：$(1,2),(2,3),(3,4)$
2. 长度 3：$(1,3),(2,4)$
3. 长度 4：$(1,4)$

这确保了计算 $m[i,j]$ 时，所有更短的子问题 $m[i,k]$ 和 $m[k+1,j]$ 已经计算完毕。

复杂度分析

指标	值
时间复杂度	$O(n^3)$
空间复杂度	$O(n^2)$
子问题数量	$\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)=O(n^2)$

章节扩展

• 14.2 矩阵链乘法 — 矩阵链乘法的完整求解过程
• 动态规划 — 动态规划完整方法论
• 最优子结构 — 最优子结构性质的详细说明

参见

• 钢条切割 — 动态规划的入门问题
• 最长公共子序列 — 另一个经典动态规划问题
• 最优二叉搜索树 — 同为 $O(n^3)$ 的动态规划问题