区间动态规划例题：矩阵连乘的最小乘法次数问题 问题描述 给定一个矩阵序列A₁,A₂,...,Aₙ，其中矩阵Aᵢ的维度为pᵢ₋₁×pᵢ。我们需要计算这些矩阵的连乘积A₁A₂⋯Aₙ。由于矩阵乘法满足结合律，不同的计算顺序会导致不同的乘法次数。要求找到一种最优的括号化方案，使得计算该连乘积所需的总标量乘法次数最少。 例如：三个矩阵A₁(10×100)、A₂(100×5)、A₃(5×50)，按(A₁A₂)A₃计算需要10×100×5+10×5×50=7500次，而按A₁(A₂A₃)计算需要100×5×50+10×100×50=75000次。 解题过程 1. 问题分析 矩阵连乘问题的关键在于确定在哪个位置"分割"矩阵序列。对于序列Aᵢ...Aⱼ，我们需要找到一个分割点k(i≤k <j)，使得先计算Aᵢ...Aₖ和Aₖ₊₁...Aⱼ，再将两个结果相乘，这样的总代价最小。 2. 状态定义 定义dp[ i][ j ]为计算矩阵链AᵢAᵢ₊₁...Aⱼ所需的最小标量乘法次数。 3. 状态转移方程 对于区间[ i,j]，考虑所有可能的分割点k(i≤k <j)： 先计算Aᵢ...Aₖ：代价为dp[ i][ k ] 再计算Aₖ₊₁...Aⱼ：代价为dp[ k+1][ j ] 最后将两个结果相乘：代价为pᵢ₋₁×pₖ×pⱼ 因此状态转移方程为： dp[ i][ j] = min{ dp[ i][ k] + dp[ k+1][ j] + pᵢ₋₁×pₖ×pⱼ } (i≤k <j) 4. 边界条件 当i=j时，只有一个矩阵，不需要乘法，故dp[ i][ i ]=0。 5. 计算顺序 由于长区间的计算依赖于短区间，我们需要按区间长度从小到大计算： 先计算所有长度为1的区间（即单个矩阵） 再计算长度为2的区间（两个矩阵相乘） 接着计算长度为3的区间，依此类推 最后计算整个区间[ 1,n ] 6. 详细计算步骤 以矩阵维度数组p=[ 10,100,5,50 ]为例（对应三个矩阵10×100、100×5、5×50）： 初始化 ：dp[ i][ i ]=0（对角线） 长度L=2 （两个矩阵）： [ 1,2]：dp[ 1][ 2 ]=10×100×5=5000 [ 2,3]：dp[ 2][ 3 ]=100×5×50=25000 长度L=3 （三个矩阵）： [ 1,3 ]：考虑k=1和k=2两种分割 k=1：dp[ 1][ 1]+dp[ 2][ 3 ]+10×100×50=0+25000+50000=75000 k=2：dp[ 1][ 2]+dp[ 3][ 3 ]+10×5×50=5000+0+2500=7500 取最小值：dp[ 1][ 3 ]=7500 7. 结果提取 最终结果为dp[ 1][ n ]，即计算整个矩阵链的最小乘法次数。 8. 算法复杂度 时间复杂度：O(n³)，需要三层循环 空间复杂度：O(n²)，用于存储dp表 这种按区间长度递增的顺序填充dp表的方法，确保了在计算每个区间时，其依赖的更短区间都已被计算完成。