参考：【动态规划】矩阵链乘法

一、问题描述

矩阵乘法分析

给定一个n个矩阵的序列（矩阵链）<A1,A2,...,An>，我们希望计算它们的乘积 A1A2...An

为了计算表达式，我们可以先用括号明确计算次序，然后利用标准的矩阵相乘算法进行计算。

完全括号化(fully parenthesized)：它是单一矩阵，或者是两个完全括号化的矩阵乘积链的积。

例如如果有矩阵链为<A1,A2,A3,A4>,则共有5种完全括号化的矩阵乘积链。
(A1(A2(A3A4)))、(A1((A2A3)A4))、((A1A2)(A3A4))、((A1(A2A3))A4)、(A1((A2A3)A4))

对矩阵链加上括号后，会对乘积运算的代价产生相当大的影响。
下面伪代码是标准的矩阵相乘，计算A*B的值给C

根据矩阵乘法的规则，当A和B相容（compatible）时，才能相乘，即A的列数和B的行数相同。例如A为A是p×q的矩阵，B是q×r的矩阵，那么乘积C是p×r的矩阵。计算C所需要时间由第8行的标量乘法的次数决定的，即pqr。

如果按照((A1A2)A3)的顺序计算：先计算A1A2(规模10×5)，需要做10*100*5=5000次标量乘法，再与A3相乘又需要做10*5*50=2500次标量乘法，共需7500次标量乘法。
如果按照(A1(A2A3))的顺序计算：先计算A2A3(规模100×50)，需100*5*50=25000次标量乘法，再与A1相乘又需10*100*50=50000次标量乘法，共需75000次标量乘法。
可见因此第一种顺序计算要比第二种顺序计算快10倍

矩阵链乘法（Matrix-chain Multiplication Problem）

给定n个矩阵的链，矩阵Ai的规模为p[i-1]xp[i] (1<=i<=n)，求完全括号化方案，使得这矩阵链的乘积所需标量乘法次数最少

注意：我们求解矩阵链乘法问题不是要求这个链的最后矩阵结果，而是确定代价最低的计算顺序。

解决方法

如果我们用暴力搜索解法一个个地找，会得到一个与n呈指数关系的时间复杂度，这是相当糟糕的。
我们或许可以试试动态规划的方法

动态规划求解

第一步 描述最优解的结构

我们用A[i..j]来表示从矩阵Ai一直乘到Aj的乘积。对于非平凡的问题，我们可以给一个分割点k将A[i..j]分为A[i..k]和A[k+1..j]。那么我们算i到j的矩阵相乘就等于两个链分别相乘的代价，加上这两个结果相乘的代价。

我们可以得到如下最优解结构：

对于原问题矩阵链的最优括号化方案中，对其子链的括号化方法，也是其子链本身的最优括号化方案

那么，我们可以将问题分为两个子问题，求出子问题的最优解，然后将子问题的最优解组合起来。

第二步 给出递归求解方案

我们令m[i,j]表示计算矩阵链A[i..j]所需标量乘法次数的最小值。那么我们最终将求解m[1,n]的值。

假设最优方案在k处分割，此时矩阵被分为A[i..k]和A[k+1..j],我们将其结果相乘时，又会产生p(i-1)p(k)p(j)的次数代价（因为Ai大小为p(i-1)p(i)，总代价计算公式之前有说）。那么对于一个非平凡解，我们有：

m[i,j]=m[i,k]+m[k+1,j]+ p(i-1)p(k)p(j)

当然，这是我们假设的最优解k，我们当然不知道哪一个是最优解，所以我们需要遍历，找到最小值。
最后得到的递归解如下：

①如果i=j，m[i,j]=0
②如果i<j，m[i,j]=min{m[i,k]+m[k+1,j]+p(i-1)p(k)p(j)} 其中i<=k<j

第三步 计算最优代价

我们用s[i,j]保存最优括号化方案的分割点位置k，即使得m[i,j]=m[i,k]+[k+1,j]+p(i-1)p(k)p(j)成立的k值

我们可以很容易地基于递归公式写出一个递归算法，但递归算法是指数时间的，并不必检查若有括号化方案的暴力搜索方法更好。
注意到，我们需要求解的不同子问题的数目是相对较少的：每对满足1<=i<=j<=n 的i和j对应一个唯一的子问题，共有n^2(最少)。递归算法会在递归调用树的不同分支中多次遇到同一个子问题。这种子问题重叠的性质是应用动态规划的另一标识(第一个标识是最优子结构)

我们采用自底向上的表格法来代替递归。 由于自底向上，我们需要以长度递增的顺序求解子问题，并按此顺序填写表m。（对于A[i..j]，其长度为j-i+1）

伪代码

下面是一个长度为6的矩阵链的m、s表：

第四步 构造最优解

每个s表中的元素记录了一个k值，指出最佳分割方案
以下伪代码代码输出最优括号化方案