问题

给定n个矩阵{A1, A2, …,An}，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。从中找出一种乘次数最少的计算次序。

问题分析

 什么是矩阵连乘

  学过线性代数的肯定懂得什么是矩阵连乘，但是在这里我还是要说一下(因为我学过线代，但是当时看见题目还是懵逼的一批)。

举个例子：
一个A矩阵：2×2和一个B矩阵：2×1再和一个C矩阵：1×3的矩阵连乘：
$\begin{vmatrix}2 & 2 \\ 1 & 3\\ \end{vmatrix} × \begin{vmatrix} 1\\ 2\\ \end{vmatrix} × \begin{vmatrix} 3&2&1 \end{vmatrix}$
这就是矩阵连乘了。

 为什么会出现乘次数不一样的情况

  由于矩阵相乘满足乘法结合律，即A×B×C=(A×B)×C=A×(B×C)，我们从实际例子上来看一下。

1. 假如我们计算(A×B)×C，先算(A×B),此时乘法次数为2×2×1=4次
$\begin{vmatrix}2 & 2 \\ 1 & 3\\ \end{vmatrix} × \begin{vmatrix} 1\\ 2\\ \end{vmatrix}= \begin{vmatrix} 6\\ 7 \end{vmatrix}$
2.我们再乘C矩阵，乘法次数为4+2×1×3=10
$\begin{vmatrix} 6\\ 7 \end{vmatrix} × \begin{vmatrix} 3&2&1 \end{vmatrix}= \begin{vmatrix} 18&12&6\\ 21&14&7 \end{vmatrix}$
1. 现在我们计算A×(B×C)，先算(B×C),此时乘法次数为2×1×3=6次
$\begin{vmatrix} 1\\ 2 \end{vmatrix} × \begin{vmatrix} 3&2&1 \end{vmatrix}= \begin{vmatrix} 3&2&1\\ 6&4&2 \end{vmatrix}$
2.我们再用A矩阵乘以刚才的结果，乘法次数为6+2×2×3=18
$\begin{vmatrix}2 & 2 \\ 1 & 3\\ \end{vmatrix} × \begin{vmatrix} 3&2&1\\ 6&4&2 \end{vmatrix}= \begin{vmatrix} 18&12&6\\ 21&14&7 \end{vmatrix}$
通过上面的两次运算，我们可以发现，在每次结合不同的矩阵，就能导致不同的乘法次数。

 为什么要用动态规划算法

  1.首先，这个问题符合最优子结构性质：问题的最优解子问题的最优解。举个简单的例子来理解这句话：一个国家里面最厉害的兵，
肯定是他所在的军营里面最厉害的兵；各个军营里面最厉害的兵，经过选拔(武举考试？)就可以有人脱颖而出，成为这个国家最厉害的
兵。
2.其次就是，重叠子问题性质：也就是少量子问题被重复解决了。说白了就是有些计算重复了，我们可以在计算第一次的时候将结果
记录下来，以后再用到的时候，直接取值，不用再去花时间计算了。

 如何用动态规划算法求解

  以A₁:50×10 A₂:10×40 A₃:40×30 A₄:30×5 为例，计算最少的乘法次数
1.我们规定m[i,j]表示第i个矩阵到第j个矩阵之间的连乘(A_i×…×A_j)的最少乘法次数，那么我们的问题就变成了求解m[1,n]。
2.我们数组p[i-1]×p[i]来表示维数矩阵的维数(也就是多少行，多少列)，比如A矩阵是50行、10列，那么矩阵A就可以表示为：
(p[0]=50)×(p[1]=10)。因此可以列出下表。

p[0]	p[1]	p[2]	p[3]	p[4]
50	10	40	30	5

  当我们准备好之后，就可以得到这么一个式子：
$m[i,j]= \begin {Bmatrix}0 &&&&& i ==j\\min(m[i,k]+m[k,j]+p[i-1]p[k]p[j])&&&&&i<j \end{Bmatrix}$
我们来理解这个式子：
1.当i==j的时候，m[i,j]表示的就是一个矩阵的乘法次数，也就是0。
2.当i<j的时候，此时的m[i,j]表示多个矩阵的连乘，将i~j个矩阵从第k个位置切开，也就
是给第i ~ k个矩阵加括号，给k ~ j个矩阵加括号，那么 矩阵连乘的次数 = 第一个矩阵连乘的次数 + 第二个矩阵连乘的次数 + 这两个矩阵连乘的次数。

接下来就是动态规划的重点环节了：填表。

i \ m[i,j] / j	1	2	3	4
1	0	20000	27000	10500
2		0	12000	8000
3			0	6000
4				0

由此我们可以知道最小的乘法次数为10500，那么这个表是怎么填，以及如何读的呢？

i	j	m[i,j]
1	1	0
2	2	0
3	3	0
4	4	0
1	2	min{m[1,1]+m[2,2]+p0p1p2}=20000
2	3	min{m[2,2]+m[3,3]+p1p2p3}=12000
3	4	min{m[3,3]+m[4,4]+p2p3p4}=6000
1	3	min{m[1,1]+m[2,3]+p0p1p3 =27000 ，m[1,2]+m[3,3]+p0p2p3 =80000}=27000
2	4	min{m[2,2]+m[3,4]+p1p2p3 =8000 ，m[1,2]+m[3,3]+p1p3p4=27000}=8000
1	4	min{m[1,1]+m[2,4]+p0p1p4 =10500 ，m[1,2]+m[3,4]+p0p2p4 =36000 ，m[1,3]+m[4,4]+p0p3p4=34500}=10500

  从这个表中我们看出填刚才那个表的顺序是按对角线进行填写.
1.当i=1，j=4的时候最小乘法次数为10500，对应的划分为m[1,1]+m[2,4]+p₀p₁p₄ =10500 ，也就是（A₁（A₂A₃A₄））
2.我们继续往下找m[2,4]对应的划分m[2,2]+m[3,4]+p1p2p3 =8000 ，也就是（A₂（A₃A₄））
3.最后我们就得到了最终的答案：（A₁（A₂（A₃A₄）））