矩阵连乘问题（最少乘法次数）

1. 问题描述

给定 $n$ 个矩阵 $A_1, A_2, \dots, A_n$，其中 $A_i$ 与 $A_{i+1}$ 是可乘的（即 $A_i$ 的列数等于 $A_{i+1}$ 的行数）。设 $A_i$ 的规模为 $p_{i-1} \times p_i$，则整个连乘积 $A_1A_2\cdots A_n$ 的规模为 $p_0 \times p_n$。

矩阵乘法满足结合律，因此可以通过加括号的方式任意改变相乘顺序。例如 4 个矩阵有 5 种加括号方式：

$$((A_1A_2)A_3)A_4 \quad (A_1(A_2A_3))A_4 \quad (A_1A_2)(A_3A_4) \quad A_1((A_2A_3)A_4) \quad A_1(A_2(A_3A_4))$$

不同的运算顺序，所需的标量乘法次数可能相差巨大。

问题：给定维度序列 $p_0, p_1, \dots, p_n$，求计算 $A_1A_2\cdots A_n$ 所需的最少标量乘法次数，并给出对应的加括号方案。

1.1 为什么乘法次数会不同？

计算两个矩阵 $A_{m \times k}$ 与 $B_{k \times n}$ 相乘，需要执行 $m \times k \times n$ 次标量乘法。

以三个矩阵 $A_1 = 10\times100$、$A_2 = 100\times5$、$A_3 = 5\times50$ 为例：

运算顺序	计算过程	乘法次数
$(A_1A_2)A_3$	$A_1A_2$：$10\times100\times5 = 5000$，得 $10\times5$；再 $\times A_3$：$10\times5\times50 = 2500$	7500
$A_1(A_2A_3)$	$A_2A_3$：$100\times5\times50 = 25000$，得 $100\times50$；再 $A_1 \times$：$10\times100\times50 = 50000$	75000

同一个连乘积，仅因为加括号方式不同，乘法次数相差 10 倍。这正是需要动态规划的原因。

1.2 约定与记号

记号	含义
$n$	矩阵个数
$p_0, p_1, \dots, p_n$	维度数组，长度为 $n+1$；$A_i$ 的规模为 $p_{i-1} \times p_i$
$A_{i..j}$	连乘积 $A_iA_{i+1}\cdots A_j$
$m[i][j]$	计算 $A_{i..j}$ 所需的最少乘法次数
$s[i][j]$	使 $m[i][j]$ 取到最小值的划分位置 $k$，用于还原最优方案

2. 为什么不能暴力枚举？

2.1 加括号方案的数量是卡特兰数

设 $P(n)$ 为 $n$ 个矩阵连乘的加括号方案数。考虑最后一次相乘：它把序列分成前 $k$ 个和后 $n-k$ 个两部分，于是

$$P(n) = \sum_{k=1}^{n-1} P(k) \cdot P(n-k), \qquad P(1) = 1$$

这是卡特兰数的递推式，解得

$$P(n) = C_{n-1} = \frac{1}{n}\binom{2n-2}{n-1}$$

$n$	1	2	3	4	5	6	10	20
方案数 $P(n)$	1	1	2	5	14	42	4862	1.77×10⁹

卡特兰数呈指数增长（$C_n \sim \dfrac{4^n}{n^{1.5}}$），因此穷举所有方案在 $n$ 稍大时即不可行。

2.2 为什么贪心法不行？

一个直觉的贪心策略是「每次优先合并当前代价最小的相邻两个矩阵」，但它不满足贪心选择性质。

反例：维度序列 $p = \{24, 38, 4, 59, 33\}$，即四个矩阵

$$A_1 = 24\times38,\quad A_2 = 38\times4,\quad A_3 = 4\times59,\quad A_4 = 59\times33$$

贪心过程（每步合并代价最小的相邻对，各步最小值唯一）：

步骤	当前序列	各相邻对代价	贪心选择	累计代价
1	$A_1A_2A_3A_4$	$24\cdot38\cdot4 = 3648$，$38\cdot4\cdot59 = 8968$，$4\cdot59\cdot33 = 7788$	合并 $A_1A_2$（3648）	3648
2	$A_{12}A_3A_4$	$24\cdot4\cdot59 = 5664$，$4\cdot59\cdot33 = 7788$	合并 $A_{12}A_3$（5664）	9312
3	$A_{123}A_4$	$24\cdot59\cdot33 = 46728$	合并（46728）	56040

最优方案 $(A_1A_2)(A_3A_4)$：

$$\underbrace{24\cdot38\cdot4}_{A_1A_2 = 3648} + \underbrace{4\cdot59\cdot33}_{A_3A_4 = 7788} + \underbrace{24\cdot4\cdot33}_{\text{两个结果相乘} = 3168} = \mathbf{14604}$$

贪心得到 56040，最优是 14604，贪心解是最优解的 3.8 倍。

关键原因：贪心只看当前这一步的局部代价，而合并出的结果矩阵维度会影响后续所有乘法的代价。第 1 步合并 $A_1A_2$ 虽然当时最便宜（3648），但它把 $A_2$ 的维度 38 与 4 合并成了 4，使第 2 步不得不在 $24\times4\times59$ 与 $4\times59\times33$ 之间继续做局部选择，最终把最贵的 $24\times59\times33$ 留到了最后一步。最优方案则宁可先付 7788 合并 $A_3A_4$，让最后一步只做 $24\times4\times33$ 的廉价乘法。局部最优无法保证全局最优，动态规划则枚举所有划分点 $k$，从全局取最优。

3. 最优子结构

定理：矩阵连乘问题具有最优子结构。即若 $A_{i..j}$ 的最优加括号方案在 $k$ 处断开（$i \le k < j$），则其中 $A_{i..k}$ 与 $A_{k+1..j}$ 的加括号方案也必定分别是各自的最优方案。

证明（剪贴法反证）：设 $A_{i..j}$ 的最优方案为 $(A_{i..k})(A_{k+1..j})$。若存在 $A_{i..k}$ 的另一种加括号方案代价更小，则用它替换后得到的 $A_{i..j}$ 的方案代价更小，与「$A_{i..j}$ 已是最优」矛盾。因此子问题的解必为最优。$\square$

有了最优子结构，就可以用子问题的最优解递推原问题的最优解。

4. 建立递归关系

4.1 状态转移方程

$$m[i][j] = \begin{cases} 0, & i = j \\[6pt] \min\limits_{i \le k < j}\Big\{\, m[i][k] + m[k+1][j] + p_{i-1} \cdot p_k \cdot p_j \,\Big\}, & i < j \end{cases}$$

三项的含义：

项	含义
$m[i][k]$	计算左半部分 $A_{i..k}$ 的代价
$m[k+1][j]$	计算右半部分 $A_{k+1..j}$ 的代价
$p_{i-1} \cdot p_k \cdot p_j$	把两个结果矩阵相乘的代价：左结果规模 $p_{i-1}\times p_k$，右结果规模 $p_k \times p_j$

最终答案是 $m[1][n]$。

4.2 重叠子问题

直接按递归关系写递归程序，会产生大量重复计算。以 $n=4$ 为例，$m[1][4]$ 的递归树为：

m[1][4]
├── k=1: m[1][1] + m[2][4]
│         └── m[2][4] → m[2][2]+m[3][4] , m[2][3]+m[4][4]
│                       └── m[2][3] → ...
├── k=2: m[1][2] + m[3][4]
│         ├── m[1][2] → ...
│         └── m[3][4] → ...
└── k=3: m[1][3] + m[4][4]
          └── m[1][3] → m[1][1]+m[2][3] , m[1][2]+m[3][3]
                        └── m[2][3] → ...   ← 与上面的 m[2][3] 重复

可以看到 $m[2][3]$、$m[1][2]$、$m[3][4]$ 等子问题被反复求解。设暴力递归的调用次数为 $T(n)$，每次调用枚举 $n-1$ 个划分点，每个划分点递归求解两侧（末尾的 $1$ 表示当前子问题自身的一次调用）：

$$T(n) = \sum_{k=1}^{n-1}\Big(T(k) + T(n-k)\Big) + 1, \qquad T(1) = 1$$

代入小规模数值可以归纳出闭式解：

$n$	1	2	3	4	5	6	10
$T(n)$	1	3	9	27	81	243	19683

即 $T(n) = 3^{\,n-1} = \Theta(3^n)$，仍是指数级。

对比：$n$ 个矩阵连乘一共有 $O(n^2)$ 个不同的子问题 $m[i][j]$，但暴力递归却要调用 $3^{n-1}$ 次——差距全在重复计算上。把每个子问题的解存进表，使每个子问题只求解一次，就能把指数级降到多项式级——这就是动态规划的核心。

5. 自底向上填表

5.1 计算顺序

$m[i][j]$ 依赖于比它更短的区间，因此按区间长度 $r = j - i + 1$ 递增的顺序填表：

for r = 2 to n:                    // 区间长度
    for i = 1 to n - r + 1:        // 区间起点
        j = i + r - 1              // 区间终点
        m[i][j] = min{ m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j] }  (i <= k < j)

$r=1$ 时 $m[i][i] = 0$（单个矩阵无需相乘），是递推的边界。

5.2 手工演算示例

取经典数据 $p = \{30, 35, 15, 5, 10, 20, 25\}$，即 6 个矩阵：

$$A_1 = 30\times35,\quad A_2 = 35\times15,\quad A_3 = 15\times5,\quad A_4 = 5\times10,\quad A_5 = 10\times20,\quad A_6 = 20\times25$$

第 1 步：$r = 2$（两个矩阵相乘）

$$m[1][2] = p_0p_1p_2 = 30\cdot35\cdot15 = 15750,\quad m[2][3] = 35\cdot15\cdot5 = 2625$$

$$m[3][4] = 15\cdot5\cdot10 = 750,\quad m[4][5] = 5\cdot10\cdot20 = 1000,\quad m[5][6] = 10\cdot20\cdot25 = 5000$$

第 2 步：$r = 3$（三个矩阵）

$$m[1][3] = \min \begin{cases} k=1: m[1][1] + m[2][3] + p_0p_1p_3 = 0 + 2625 + 30\cdot35\cdot5 = 7875 \\ k=2: m[1][2] + m[3][3] + p_0p_2p_3 = 15750 + 0 + 30\cdot15\cdot5 = 18000 \end{cases} = 7875 \quad (k=1)$$

同理 $m[2][4] = \min\{6000, 4375\} = 4375$（$k=3$），$m[3][5] = \min\{2500, 3750\} = 2500$（$k=3$），$m[4][6] = \min\{6250, 3500\} = 3500$（$k=5$）。

第 3 步：$r = 4, 5$

$$m[1][4] = \min\{14875,\ 21000,\ 9375\} = 9375 \ (k=3)$$

$$m[2][5] = \min\{13000,\ 7125,\ 11375\} = 7125 \ (k=3)$$

$$m[3][6] = \min\{5375,\ 9500,\ 10000\} = 5375 \ (k=3)$$

$$m[1][5] = \min\{28125,\ 27250,\ 11875,\ 15375\} = 11875 \ (k=3)$$

$$m[2][6] = \min\{18500,\ 10500,\ 18125,\ 24625\} = 10500 \ (k=3)$$

第 4 步：$r = 6$（原问题）

$$m[1][6] = \min \begin{cases} k=1: m[1][1] + m[2][6] + p_0p_1p_6 = 0 + 10500 + 30\cdot35\cdot25 = 36750 \\ k=2: m[1][2] + m[3][6] + p_0p_2p_6 = 15750 + 5375 + 30\cdot15\cdot25 = 32375 \\ k=3: m[1][3] + m[4][6] + p_0p_3p_6 = 7875 + 3500 + 30\cdot5\cdot25 = \mathbf{15125} \\ k=4: m[1][4] + m[5][6] + p_0p_4p_6 = 9375 + 5000 + 30\cdot10\cdot25 = 21875 \\ k=5: m[1][5] + m[6][6] + p_0p_5p_6 = 11875 + 0 + 30\cdot20\cdot25 = 26875 \end{cases} = \mathbf{15125} \quad (k=3)$$

5.3 完整 $m$ 表与 $s$ 表

$m$ 表（下三角无意义，用 - 表示；上三角为 $i < j$ 的有效值）：

$i \backslash j$	1	2	3	4	5	6
1	0	15750	7875	9375	11875	15125
2	-	0	2625	4375	7125	10500
3	-	-	0	750	2500	5375
4	-	-	-	0	1000	3500
5	-	-	-	-	0	5000
6	-	-	-	-	-	0

$s$ 表（记录最优划分点 $k$）：

$i \backslash j$	1	2	3	4	5	6
1	0	1	1	3	3	3
2	-	0	2	3	3	3
3	-	-	0	3	3	3
4	-	-	-	0	4	5
5	-	-	-	-	0	5
6	-	-	-	-	-	0

结论：最少乘法次数为 15125，最优加括号方案为 $((A_1(A_2A_3))((A_4A_5)A_6))$。

对比：若按从左到右顺序相乘 $((((A_1A_2)A_3)A_4)A_5)A_6$，代价为 $15750 + 2250 + 1500 + 6000 + 15000 = 40500$，是最优方案的 2.68 倍。

6. 构造最优解

$m$ 表只给出了最优值，要得到具体的加括号方案，需要额外的 $s$ 表：在计算 $m[i][j]$ 取到最小值时，同时记录划分点 $k$。之后从 $s[1][n]$ 开始自顶向下回溯：

/** 由 s 表自顶向下回溯，输出最优加括号方案 */
private String buildOptimalParens(int i, int j) {
    if (i == j) {                       // 单个矩阵，递归出口
        return "A" + i;
    }
    int k = s[i][j];                    // 最优划分点
    return "(" + buildOptimalParens(i, k)
               + buildOptimalParens(k + 1, j) + ")";
}

回溯过程（$n=6$）：

s[1][6] = 3  →  ( A1..A3 )( A4..A6 )
s[1][3] = 1  →  ( A1 )( A2..A3 )
s[2][3] = 2  →  ( A2 )( A3 )
s[4][6] = 5  →  ( A4..A5 )( A6 )
s[4][5] = 4  →  ( A4 )( A5 )

合并结果：((A1(A2A3))((A4A5)A6))

7. Java 完整实现

import java.util.Arrays;

/**
 * 矩阵连乘问题：求计算 A1A2...An 所需的最少标量乘法次数，并给出最优加括号方案。
 */
public class MatrixChain {

    /** 维度数组 p：第 i 个矩阵 Ai 的规模为 p[i-1] × p[i]，长度为 n+1 */
    private final int[] p;
    /** m[i][j]：计算 Ai..Aj 所需的最少乘法次数，仅用 1..n 下标 */
    private final long[][] m;
    /** s[i][j]：使 m[i][j] 取到最小值的划分位置 k，用于回溯构造最优解 */
    private final int[][] s;
    private final int n;

    public MatrixChain(int[] p) {
        this.p = p;
        this.n = p.length - 1;
        this.m = new long[n + 1][n + 1];
        this.s = new int[n + 1][n + 1];
    }

    /** 自底向上动态规划：按链长 r 递增填表，时间复杂度 O(n^3)，空间复杂度 O(n^2) */
    public long solve() {
        // 链长为 1 时无需相乘，代价为 0（m 数组默认即为 0）
        for (int r = 2; r <= n; r++) {              // r 为子链长度
            for (int i = 1; i <= n - r + 1; i++) {  // i 为子链起点
                int j = i + r - 1;                  // j 为子链终点
                m[i][j] = Long.MAX_VALUE;
                for (int k = i; k < j; k++) {       // 枚举最后一次相乘的划分点
                    long cost = m[i][k] + m[k + 1][j]
                            + (long) p[i - 1] * p[k] * p[j];
                    if (cost < m[i][j]) {
                        m[i][j] = cost;
                        s[i][j] = k;
                    }
                }
            }
        }
        return m[1][n];
    }

    /** 由 s 表自顶向下回溯，输出最优加括号方案，如 ((A1(A2A3))((A4A5)A6)) */
    public String buildOptimalParens() {
        return buildOptimalParens(1, n);
    }

    private String buildOptimalParens(int i, int j) {
        if (i == j) {
            return "A" + i;
        }
        int k = s[i][j];
        return "(" + buildOptimalParens(i, k) + buildOptimalParens(k + 1, j) + ")";
    }

    /** 打印 m 表和 s 表的上三角部分，便于人工核对填表过程 */
    public void printTables() {
        System.out.println("m 表（最少乘法次数）：");
        for (int i = 1; i <= n; i++) {
            StringBuilder line = new StringBuilder();
            for (int j = 1; j <= n; j++) {
                line.append(j < i ? String.format("%10s", "-") : String.format("%10d", m[i][j]));
            }
            System.out.println(line);
        }
        System.out.println("s 表（最优划分点 k）：");
        for (int i = 1; i <= n; i++) {
            StringBuilder line = new StringBuilder();
            for (int j = 1; j <= n; j++) {
                line.append(j < i ? String.format("%5s", "-") : String.format("%5d", s[i][j]));
            }
            System.out.println(line);
        }
    }

    /** 备忘录法（自顶向下递归 + 记忆化），与自底向上 DP 结果一致 */
    public static long memoized(int[] p) {
        int n = p.length - 1;
        long[][] memo = new long[n + 1][n + 1];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }
        return lookup(p, memo, 1, n);
    }

    private static long lookup(int[] p, long[][] memo, int i, int j) {
        if (i == j) {
            return 0;
        }
        if (memo[i][j] >= 0) {           // 查表命中，直接返回，避免重复计算
            return memo[i][j];
        }
        long best = Long.MAX_VALUE;
        for (int k = i; k < j; k++) {
            best = Math.min(best, lookup(p, memo, i, k) + lookup(p, memo, k + 1, j)
                    + (long) p[i - 1] * p[k] * p[j]);
        }
        memo[i][j] = best;               // 记录子问题解
        return best;
    }

    public static void main(String[] args) {
        // 六个矩阵：A1=30×35, A2=35×15, A3=15×5, A4=5×10, A5=10×20, A6=20×25
        int[] p = {30, 35, 15, 5, 10, 20, 25};

        MatrixChain chain = new MatrixChain(p);
        long min = chain.solve();
        System.out.println("最少乘法次数：" + min);
        System.out.println("最优加括号方案：" + chain.buildOptimalParens());
        System.out.println("备忘录法校验：" + memoized(p));
        System.out.println();
        chain.printTables();

        // 对比：顺序相乘 ((((A1A2)A3)A4)A5)A6) 的代价
        long leftToRight = 0;
        for (int i = 1; i < p.length - 1; i++) {
            leftToRight += (long) p[0] * p[i] * p[i + 1];
        }
        System.out.println();
        System.out.println("从左到右顺序相乘的代价：" + leftToRight);
    }
}

7.1 运行结果

最少乘法次数：15125
最优加括号方案：((A1(A2A3))((A4A5)A6))
备忘录法校验：15125

m 表（最少乘法次数）：
         0     15750      7875      9375     11875     15125
         -         0      2625      4375      7125     10500
         -         -         0       750      2500      5375
         -         -         -         0      1000      3500
         -         -         -         -         0      5000
         -         -         -         -         -         0
s 表（最优划分点 k）：
    0    1    1    3    3    3
    -    0    2    3    3    3
    -    -    0    3    3    3
    -    -    -    0    4    5
    -    -    -    -    0    5
    -    -    -    -    -    0

从左到右顺序相乘的代价：40500

输出与第 5 节的手工演算完全一致。

8. 复杂度分析

8.1 时间复杂度

• 外层按链长 $r$ 循环：$O(n)$ 种链长；
• 中层枚举起点 $i$：共 $O(n)$ 个；
• 内层枚举划分点 $k$：最多 $O(n)$ 个。

三层循环嵌套，总时间复杂度为

$$O(n) \times O(n) \times O(n) = O(n^3)$$

相比暴力递归的 $\Theta(3^n)$，是数量级的改进。$n=20$ 时，暴力递归需调用 $3^{19} \approx 1.16\times10^9$ 次，而动态规划的三重循环只需执行

$$\sum_{r=2}^{n}(n-r+1)(r-1) = \binom{n+1}{3} = \binom{21}{3} = 1330$$

次基本运算。

8.2 空间复杂度

需要两个 $(n+1)\times(n+1)$ 的二维数组（$m$ 表与 $s$ 表），故为 $O(n^2)$。

8.3 可优化点

优化方向	说明	效果
只保留 $s$ 表 + 滚动数组	求最优值时 $m$ 表可用一维滚动数组按链长递推	空间降到 $O(n)$（但还原方案仍需 $s$ 表，实际意义有限）
四边形不等式优化	最优划分点满足 $s[i][j-1] \le s[i][j] \le s[i+1][j]$，可把 $k$ 的枚举范围收窄到 $O(n)$ 总量	时间降到 $O(n^2)$
记忆化搜索	只计算真正用到的子问题，适合某些子问题不需要求解的场景	时间不变，常数更小

8.4 备忘录法 vs 自底向上

对比项	备忘录法（自顶向下）	自底向上填表
代码风格	与递归关系式几乎一一对应，易读	需要自己确定填表顺序
递归开销	有函数调用栈开销，$n$ 很大时可能栈溢出	无
计算范围	只算被用到的子问题	全部子问题都要算
空间优化	不易做滚动数组	容易做

本问题中所有子问题都会被用到，因此两种方式效率相当，结果也完全一致（见运行结果中的「备忘录法校验：15125」）。

9. 考点小结与常见变形

9.1 解题四步

1. 状态定义：$m[i][j]$ = 计算 $A_{i..j}$ 的最少乘法次数；
2. 递归关系：$m[i][j] = \min_{i \le k < j}\{m[i][k] + m[k+1][j] + p_{i-1}p_kp_j\}$；
3. 计算顺序：按区间长度 $r$ 递增；
4. 构造最优解：用 $s$ 表回溯输出加括号方案。

9.2 易错点

• 维度数组下标：$A_i$ 是 $p_{i-1}\times p_i$，写成 p[i]*p[j] 是常见错误，最后一项应为 $p_{i-1}\cdot p_k \cdot p_j$。
• 区间长度还是终点：外层循环必须是区间长度 $r$，不能直接用 $j$，否则计算 $m[i][j]$ 时依赖的子问题尚未求出。
• 乘法溢出：$p_{i-1}p_kp_j$ 在维度较大时会超出 int 范围，应使用 long（代码中已强制转换 (long)）。
• 只求值不求解：若题目要求给出加括号方案，必须额外维护 $s$ 表，否则只能得到最小次数。

9.3 同族变形

变形	与矩阵连乘的关系
石子合并（环形 / 直线）	完全相同的区间 DP 结构，代价函数换成两堆石子重量之和
最优二叉搜索树	状态与三重循环结构一致，代价函数换成查找概率加权和
多边形三角剖分	与矩阵连乘一一对应，最小权三角剖分 = 最少乘法次数
括号匹配加最少括号	区间 DP，状态为「区间内最少需要补充的括号数」
最长回文子序列	区间 DP，状态为「区间内最长回文子序列长度」

区间 DP 的通用特征：状态为 dp[i][j] 表示区间 $[i, j]$ 上的最优解，转移时枚举分割点 $k$，按区间长度递增填表。矩阵连乘是这类问题最经典的入门模型。

9.4 与软考的联系

在软考中级「软件设计师」下午场算法题中，矩阵连乘属于动态规划的经典考点，常见考法：

• 补全 $m[i][j]$ 的递推式与三重循环的填空；
• 给定小规模维度序列，手工填写 $m$ 表并求最少乘法次数；
• 给出 $s$ 表，要求写出最优加括号方案。