[动态规划] 矩阵链乘法

讲解：

个矩阵相乘时，

为

行

列的矩阵，以

为例进行分析，这些矩阵的乘积有多种计算顺序。举个例子，我们按习惯的从左到右的顺序进行计算时可以写作

，从左到右计算时可以写作

。除此之外还有

等等，计算的顺序多种多样。这些计算顺序得出的结果（矩阵链乘积）完全相同，但不同顺序下的 “ 乘法运算次数 ” 会有所差异。

处理矩阵链乘法问题时，如果检查所有可能的计算顺序，那么算法的复杂度将达到

。不过，由于这个问题能够分割成更小的局部问题，我们可以运用动态规划法。

首先，

只有一种计算方法（顺序），需要

次乘法运算。同理，

也只有一种计算方法，需要

次乘法运算。归纳后可知，

只有一种计算方法，需要

次乘法运算。于是我们将这些运算次数视为 “ 成本 ” 记录在表中。

接下来求

的最优计算方法。举个例子，计算

的最优计算方法时，我们要分别算出

与

的成本，取其中最小的一个作为

的成本记录在表中。这里：

• 

  的成本

  

  

  的成本

  

  

  的成本

  

  

• 

  的成本

  

  

  的成本

  

  

  的成本 

  

请注意，这一步用到的

和

的成本可以直接从表中引用，不需要再进行计算。另外还要注意，当 

时，

的成本为 

。

一般情况下，矩阵链乘法

的最优解就是

的最小成本（其中

）。

举个例子，

时的最优解就是下列式子中的最小值。

• 

  的成本

  

  

  的成本

  

  

  的成本

  

  

• 

  的成本

  

  

  的成本

  

  的成本

  

• 

  的成本

  

  的成本

  

  的成本

  

• 

  的成本

  

  的成本

  

  的成本

  

  

现在来看看这个算法的具体实现方法。先准备下述变量。

	该二维数组中， 表示计算 时所需要乘法运算的最小次数
	该一位数组用于储存矩阵的行列数，其中 是 的矩阵

利用上述变量，我们可以利用下面的式子求出

。

这个算法的实现方法如下：

matrixChainMultiplication()
    for i = 1 to n
        m[i][j] = 0

    for l = 2 to n
        for i = 1 to n - l + 1
            j = i + l - 1
            m[i][j] = INFTY
            for k = i to j - 1
                m[i][j] = min(m[i][j], m[i][k] + m[k + l][j] + p[i - l] * p[k] * p[j])
           

考察：这个算法需要让对象的矩阵对象的数量

从

逐步增加到

，同时对于每个

要通过不断改变

和

来改变指定范围。除此之外，还需要在

和

的范围内让 

不断变化。整个算法由三重循环构成，因此复杂度为 

。

#include <iostream>
#include <algorithm>
using namespace std;

static const int N = 100;

int main() {
    int n, p[N + 1], m[N + 1][N + 1];
    cin >> n;
    
    for (int i = 1; i <= n; i++）
        cin >> p[i - 1] >> p[i];

    for (int i = 1; i <= n; i++) m[i][j] = 0;
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = (1 << 21);
            for (int k = i; k <= j - 1; k++)
                m[i][j] = min(m[i][j], m[i][k] + m[k + l][j] + p[i - l] * p[k] * p[j]);
        }
    }

    cout << m[l][n] << endl;

    return 0;
}