矩阵连乘的最小乘法次数问题

题目描述
给定一个数组 p[]，其中 p[i-1] 和 p[i] 分别表示第 i 个矩阵的行数和列数（矩阵 A_i 的维度为 p[i-1] × p[i]）。要求计算这些矩阵连乘的最小乘法次数。矩阵乘法满足结合律，不同的结合顺序会导致乘法次数差异巨大。

例如：三个矩阵 A1(10×30)、A2(30×5)、A3(5×60)，按 (A1A2)A3 顺序乘需要 10×30×5 + 10×5×60 = 1500 + 3000 = 4500 次乘法；按 A1(A2A3) 顺序需要 30×5×60 + 10×30×60 = 9000 + 18000 = 27000 次。目标是找到最小乘法次数的结合顺序。

解题过程

1. 问题分析

   • 矩阵连乘的结果与结合顺序无关，但乘法次数与顺序强相关。
   • 若将矩阵链划分为两部分：A_i...A_k 和 A_{k+1}...A_j，则总乘法次数 = 左部分次数 + 右部分次数 + 合并两部分的次数（即 p[i-1] × p[k] × p[j]）。
   • 问题具有最优子结构：整个链的最优解包含子链的最优解。

2. 定义状态

   • 设 dp[i][j] 表示计算矩阵链 A_i...A_j 所需的最小乘法次数（1 ≤ i ≤ j ≤ n，n 为矩阵个数）。
   • 初始条件：当 i = j 时，单个矩阵无需乘法，dp[i][i] = 0。

3. 状态转移方程

   • 对于 i < j，枚举分割点 k（i ≤ k < j），将链分为 A_i...A_k 和 A_{k+1}...A_j。
   • 合并两部分的乘法次数为 p[i-1] × p[k] × p[j]（因为左部分矩阵维度为 p[i-1] × p[k]，右部分为 p[k] × p[j]）。
   • 转移方程：

     dp[i][j] = min_{i ≤ k < j} { dp[i][k] + dp[k+1][j] + p[i-1] × p[k] × p[j] }
     

4. 计算顺序

   • 按区间长度 L = j - i 从小到大计算（L 从 1 到 n-1）。
   • 对于每个 L，枚举起点 i，计算终点 j = i + L，再枚举分割点 k。

5. 示例演算
   以 p = [10, 30, 5, 60]（对应三个矩阵 A1(10×30)、A2(30×5)、A3(5×60)）为例：

   • 初始化：dp[1][1]=0, dp[2][2]=0, dp[3][3]=0。
   • L=1：
     • dp[1][2] = min( dp[1][1] + dp[2][2] + 10×30×5 ) = 0 + 0 + 1500 = 1500
     • dp[2][3] = min( dp[2][2] + dp[3][3] + 30×5×60 ) = 0 + 0 + 9000 = 9000
   • L=2：
     • dp[1][3] = min( k=1: dp[1][1] + dp[2][3] + 10×30×60 = 0 + 9000 + 18000 = 27000, k=2: dp[1][2] + dp[3][3] + 10×5×60 = 1500 + 0 + 3000 = 4500 ) = 4500
   • 最终结果：dp[1][3] = 4500。

6. 算法复杂度

   • 时间复杂度 O(n³)，空间复杂度 O(n²)。

通过以上步骤，可系统地求出任意矩阵链乘的最小乘法次数。