矩阵连乘的最小乘法次数问题 题目描述 给定一个矩阵序列A₁, A₂, ..., Aₙ，其中矩阵Aᵢ的维度为pᵢ₋₁ × pᵢ（i从1到n），要求计算这些矩阵连乘A₁A₂...Aₙ的最小乘法次数。矩阵乘法满足结合律，不同的加括号方式（即不同的计算顺序）会导致不同的乘法次数。目标是找到一种加括号方式，使得总的标量乘法次数最少。 解题过程 理解矩阵乘法的成本 若矩阵A是m×n的，矩阵B是n×p的，则计算AB需要m×n×p次标量乘法。例如，A₁(10×30)乘A₂(30×5)需要10×30×5=1500次乘法。 问题分析 矩阵连乘的不同加括号方式会导致不同的计算成本。例如三个矩阵A(10×30)、B(30×5)、C(5×60)： 先算(AB)C：成本=10×30×5 + 10×5×60 = 1500 + 3000 = 4500 先算A(BC)：成本=30×5×60 + 10×30×60 = 9000 + 18000 = 27000 可见选择顺序对成本影响巨大。 定义状态 设dp[ i][ j ]表示计算矩阵链AᵢAᵢ₊₁...Aⱼ（i≤j）所需的最小乘法次数。 状态转移方程 对于区间[ i, j]，我们尝试在所有可能的分割点k（i ≤ k < j）处将矩阵链分成两部分：(Aᵢ...Aₖ)和(Aₖ₊₁...Aⱼ)。则： dp[ i][ j] = min{ dp[ i][ k] + dp[ k+1][ j] + pᵢ₋₁ × pₖ × pⱼ }，对所有k∈[ i, j-1 ] 其中pᵢ₋₁ × pₖ × pⱼ是合并左右两部分结果的乘法成本。 初始化 单个矩阵不需要乘法：dp[ i][ i ] = 0（对所有i） 其他dp[ i][ j ]初始化为一个大数（如∞） 计算顺序 按区间长度L从2到n（L = j-i+1）递增计算： L=2：计算所有长度为2的区间[ i, i+1 ] L=3：计算所有长度为3的区间[ i, i+2 ] ... L=n：计算整个区间[ 1, n ] 示例演算 给定矩阵链：A₁(30×35)、A₂(35×15)、A₃(15×5)、A₄(5×10)、A₅(10×20)、A₆(20×25)，p数组=[ 30,35,15,5,10,20,25 ]。 L=2 ： dp[ 1][ 2 ] = 30×35×15 = 15750 dp[ 2][ 3 ] = 35×15×5 = 2625 dp[ 3][ 4 ] = 15×5×10 = 750 dp[ 4][ 5 ] = 5×10×20 = 1000 dp[ 5][ 6 ] = 10×20×25 = 5000 L=3 （以dp[ 1][ 3 ]为例）： k=1：dp[ 1][ 1]+dp[ 2][ 3 ]+30×35×5 = 0+2625+5250 = 7875 k=2：dp[ 1][ 2]+dp[ 3][ 3 ]+30×15×5 = 15750+0+2250 = 18000 取最小值7875 继续计算所有区间，最终dp[ 1][ 6 ]=15125即为最小乘法次数。 复杂度分析 时间复杂度：O(n³)，三层循环（区间长度、起点、分割点） 空间复杂度：O(n²)，存储dp表 通过这种自底向上的区间DP方法，可以高效解决矩阵连乘的最小乘法次数问题。