算法：矩阵连乘求的最小乘法次数

今天来讨论一道算法题，这道算法题我在做的时候真的是没什么思路，甚至看到解法之后依然想了好久才想明白，好久没看过算法了，本来对动态规划这块就不是很熟，这里记录一下。

题目

给定一个 n 的矩阵序列，我们希望计算它们的乘积：

其中， 是 矩阵

注意，这里不是要计算乘积，而是希望找到一个明确的计算次序，使得这个矩阵连乘的乘法次数最少，并求这个最小的乘法次数（，这个值表示第 1 个到第 n 个矩阵相乘的最小乘法次数）。下面举举几个例子：

当 时，；
当 时，；
当 时，有两种情况：

1. ，这乘法次数为：；
2. ，这乘法次数为：；

而，

简单来说，这道题的目的，就是在计算矩阵连乘时，求出一种方案，使得计算所需的乘法次数最小，输出的结果是这个最小的乘法次数。

暴力穷尽解法

能想到的第一种方案就是，穷举法，这里不讲述穷举法如何解决上面的问题，主要来看下穷举法的复杂度，假设 表示对于一个 n 个矩阵连乘时可选的方案数（穷举法，需要计算每个方案最后的结果，然后选择最小的一个），那么其实是可以得到下面的递推公式的：

对于一个 n 个矩阵连乘情况，我们在矩阵中选择一个 k 点，将一个大矩阵分成两个小矩阵，然后分别求其可选的方案数，结果相乘，就是此时的总方案数。那么这种暴力穷尽解法的时间复杂度是多少呢？

这个时间复杂度其实是：，我们来证明一下：

假设

1. 当 时，；
2. 当 时，；

所以，当 ，即 时， ；

因此，，这种暴力穷尽解法的时间复杂度是 。

时间复杂度是与 n 呈指数关系，这种方案明显是一个糟糕的选择。

动态规划解法

前面的穷举法时间度过高，明显是不可取，那么应该怎么去优化这个问题呢？这里介绍一种使用动态规划的解法。

子问题拆分

其实，在前面的穷尽法中有一个可取的地方，那就是子问题的拆分，在 中，先选择一个矩阵 ，这样的话就将一个大矩阵拆分为两个小矩阵，分别求这两个小矩阵的最小乘法次数，然后再将 i 从 遍历一边，取一个最小值，就可以得到我们想要的结果。

最开始考虑这个问题时，当时没想明白，一个大矩阵的最优解怎么拆分为两个小矩阵的最优解，忘记了最外围还有一个遍历，然后再取最优解。

这是一种非常有用算法思想，将一个大问题拆分为一些子（小）问题，先解决这些小问题，最后大问题就迎刃而解了，其实跟递归、分治这些思想都有一些类似之处。

递推公式推导

在 中，选择一个矩阵 将一个大矩阵拆分为 和 的问题，最后把这两个做乘就可以得到最后的结果，，因此，可以得到（k 为最佳切分点时）：

上面的公式是假设 为最佳的切分点，但是实际上这个是无法判断的，对于
，k 是有 种可能的值，最优的切分点必然在这其中，只需要遍历求最优解即可，最后的递推公式为：

到这里，最优解的递推公式就推导完成了，那么如何求解呢？

计算最小的乘法次数

有了前面的递推公式，下面就看如何根据这个递推去求最优解？

递归算法

如果直接按照递推公式去设计程序，其实现如下：

public int countMatricsChain(int[] a, int i, int j, int[][] m) {
    if (i == j) {
        return 0;
    }
    m[i][j] = Integer.MAX_VALUE;
    for (int k = 0; k < j - 1; k++) {
        int q =
            countMatricsChain(a, i, k, m) + countMatricsChain(a, k + 1, j, m) + a[i] * a[k
                + 1] * a[j+1];
        if (q < m[i][j]) {
            m[i][j] = q;
        }
    }
    return m[i][j];
}

这时的时间复杂度也将是指数时间，与暴力穷尽解法区别并不大。其时间复杂度的分析如下：

这里假设 为计算 n 个矩阵相乘的最优解的所花费的时间，那么得到下面的公式：

1. ；
2. ；

上面的公式，可以简化为：

下面还是根据代入法证明：

这里先根据数据归纳法证明：对于所有的 都成立， 的时候很简单，当 时，有：

这里可以看到，即使使用前面分析的递推公式去做，最后解法的时间复杂度依然是 ，那么有没有更好的解法呢？

动态规划求解

其实，关于动态规划问题，有一个非常明显的特点就是重叠子问题，上面的解法之所以时间复杂度那么高，一个重要的原因就是在使用递归方法时，有很多重复的计算，比如对于 这个值，其实 都会用到，如何防止重复计算将是这个问题优化的一个重点，容易想到的方法就是使用空间换时间，在计算的过程中，额外申请一个二维数组（）保存 这个值，避免重复计算。

这个二维数据，也类似一个表格，下面的问题就是怎么填充这个表格（这个解法在算法导论上叫做自底向上的表格填充法）

关于表格这个说法，之前没有听说过，这是第一次听说，当时在做这道题的时候真的是有点脑子转不过来。

这里，我们举个例子，有一个表格如下，首先，我们有：

所以表格对角线上的值均为0，因为是要求 的，所以这个表格对角线下面的空格的值是不需要去填充的。

假设这里，我们要去求 （图中红色的空格），根据 这个公式，其实是需要下面几个空格的值（图中黄色空格的数值）：

1. ；
2. ；
3. ；
4. ；
5. ；

这里是有一个规律的，那就是上面的值均在红线以下。而且最开始的对角线的值是有的，所以将对角线依次往右上方平移去计算，这样的话，在求 时，其所需要的值都是已知的。

表格填充法

右上角的深红色的点，就是我们要求解的最优解。

这部分的代码实现如下：

// a[0] 不使用，使用的是，1到 n+1
public int countMatricsChain(int[] a, int n) {
    int[][] m = new int[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        m[i][i] = 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] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k + 1][j] + a[i] * a[k + 1] * a[j + 1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                }
            }
        }
    }
    return m[1][n];
}

关于这个时间复杂度比较容易求解，是 。

平衡树描述问题

这里介绍另一种思路去理解这里问题，就是平衡树的思想（其实用平衡树去理解反而有些难度，不过明白这道题的解法之后再看就清晰很多），我们可以把上面的矩阵想象成一棵树最下面的子节点，这棵树的深度是 ，在处理矩阵相乘时，其实每一层都会合并一颗子树（且只会合并一棵树），过程如下图：

用平衡树的思想

其中， 分别为最佳的计算点。其实，上面的图只是其中一个切分过程，因为最佳计算点的值无法判断的。

自己在做的时候，开始有一个地方没明白：那就是将一颗树分为两棵树求解时，一棵树的最优解怎么转化为两个树最优解求解，因为当时想着还有最后一步合并，所以还会有一个变量，没有理解上面的拆分怎么成立，知道了最后的解法再去看就容易理解了，只要保证两颗子树是最优解，然后再加上那个变量（最后一步的矩阵相乘），遍历整个拆分点即可选择最小值即可，当时这一步没有转过来。

总结

其实这道题，算是一道常规题，如果对动态规划熟悉的，是很容易解决的，动态规划的题是有一套专门的解题方式/思想，说到底，还是自己的算法基础比较弱，之前并没有仔细看过动态规划的内容，希望自己能按照耗子叔的 ARTS 计划，保持每周学习一道算法题，坚持下去，来弥补这块的短板。

---

参考：

• 《算法导论》；