获取最佳矩阵链相乘方法

【出自XM面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

给定一个矩阵序列，找到最有效的方式将这些矩阵相乘在一起。给定表示矩阵链的数组p[]，使得第i个矩阵Ai的维数为p[i-1]×p[i]。编写一个函数MatrixChainOrder（），该函数应该返回乘法运算所需的最小乘法数。

输入：p[]={40，20，30，10，30}

输出：26000

有4个大小为40×20、20×30、30×10和10×30的矩阵。假设这四个矩阵为A、B、C和D，该函数的执行方法可以使执行乘法运算的次数最少。

分析与解答：

该问题实际上并不是执行乘法，而只是决定以哪个顺序执行乘法。由于矩阵乘法是关联的，所以有很多选择来进行矩阵链的乘法运算。换句话说，无论采用哪种方法来执行乘法，结果将是一样的。例如，如果有四个矩阵A、B、C和D，可以有如下几种执行乘法的方法：

（ABC）D=（AB）（CD）=A（BCD）=…

虽然这些方法的计算结果相同。但是，不同的方法需要执行乘法的次数是不相同的，因此效率也是不同的。例如，假设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次。(www.xing528.com)

显然，第一种方法需要执行更少的乘法运算，因此效率更高。

对于本题中示例而言，执行乘法运算的次数最少的方法如下：

（A（BC））D的执行乘法运算的次数为20*30*10+40*20*10+40*10*30。

方法一：递归法

最简单的方法就是在所有可能的位置放置括号，计算每个放置的成本并返回最小值。在大小为n的矩阵链中，可以以n-1种方式放置第一组括号。例如，如果给定的链是4个矩阵。（A）（BCD）、（AB）（CD）和（ABC）（D）中，有三种方式放置第一组括号。每个括号内的矩阵链可以被看作较小尺寸的子问题。因此，可以使用递归方便地求解。递归的实现代码如下：

程序的运行结果如下：

最少的乘法次数为42

这种方法的时间复杂度是指数级的。可以注意到，这种算法会对一些子问题进行重复的计算。例如在计算（A）（BCD）这种方案的时候会计算C*D的代价，而在计算（AB）（CD）这种方案的时候又会重复计算C*D的代价。显然子问题是有重叠的，对此，通常可以用动态规划的方法来降低时间复杂度。

方法二：动态规划

典型的动态规划的方法是使用自下而上的方式来构造临时数组以保存子问题的中间结果，从而可以避免大量重复的计算。实现代码如下：

算法性能分析：

这种方法的时间复杂度为O（n^3），空间复杂度为O（n^2）。