矩阵链乘法

算法

矩阵链乘法问题是指在给定一系列矩阵的情况下,找到一种最优的括号化方式,使得矩阵相乘的计算次数最少。该问题可以通过动态规划高效解决。

时间复杂度:最佳 O(n³) | 平均 O(n³) | 最差 O(n³)
空间复杂度:O(n²)

应用场景/前提条件

  • 动态规划
  • 矩阵乘法
  • 二维动态规划表

算法讲解

矩阵链乘法

介绍

矩阵链乘法(Matrix Chain Multiplication)是一个经典的动态规划问题,给定一系列矩阵,找出相乘的最佳顺序以最小化总的基本运算次数。由于矩阵乘法满足结合律(即(A×B)×C = A×(B×C)),不同的计算顺序会导致相同的结果,但计算量可能差异巨大。

问题定义

给定n个矩阵的链:A₁×A₂×...×Aₙ,其中矩阵Aᵢ的维度为pᵢ₋₁×pᵢ(即行数×列数),目标是找到一种最优的计算顺序,实现完成整个矩阵链的乘法运算所需的标量乘法次数最少。

矩阵乘法的计算代价可以用以下方式定义:两个矩阵A(m×n)和B(n×p)相乘,需要进行m×n×p次标量乘法运算。例如,计算一个2×3矩阵和一个3×4矩阵的乘积,需要2×3×4=24次乘法运算。

不同的乘法顺序会产生截然不同的计算代价。比如三个矩阵A₁(10×100)、A₂(100×5)和A₃(5×50)的乘法:

  • 按照(A₁×A₂)×A₃的顺序:A₁×A₂需要10×100×5=5000次乘法,结果是一个10×5的矩阵;然后与A₃相乘需要10×5×50=2500次乘法,共需要7500次乘法运算。
  • 按照A₁×(A₂×A₃)的顺序:A₂×A₃需要100×5×50=25000次乘法,结果是一个100×50的矩阵;然后与A₁相乘需要10×100×50=50000次乘法,共需要75000次乘法运算。

通过上述例子我们发现,选择不同的计算顺序可能导致运算次数相差十倍以上。随着矩阵数量的增加,可能的括号方案数量呈指数级增长,穷举所有可能的顺序基本不可行。

矩阵链乘法问题的挑战在于,对于n个矩阵的乘积,有卡特兰数量级的不同括号方案。使用动态规划,我们可以在O(n³)的时间复杂度内找到最优解。

算法步骤

  1. 创建一个表dp[i][j]存储从第i个矩阵到第j个矩阵的最小计算代价

...