目录

1.两个矩阵相乘

2. 三个矩阵相乘

3.n个矩阵相乘与动态规划递推公式 

4.伪代码 

 5.伪代码实现

对于两个矩阵乘法：A(row1,col1)*B(row2,col2)=C(row3,col3)

有以下性质：

1.row3 = row1

2.col3 = col1

3.col1 = row2

4.乘法次数 = row1*col1*col2。（C中的元素(i,j)是由A中的第i行与B中的第j列中的元素对应乘而来，而C中又有row1*col2个这样的元素）。

再来考虑下三个矩阵相乘A1A2A3。

可以是（A1A2）A3也可以是A1（A2A3）。

而两种算式虽然结果是一样的，但是过程中需要计算的乘法次数是不一样的。

如以下例子：

3个矩阵{A1, A2, A3}连乘，设3个矩阵的维数分别为10×100, 100×5, 5×50。

若按((A1A2)A3)计算，需要数乘次数为：10×100×5+10×5×50=7500；

若按(A1(A2A3))计算，需要数乘次数为：100×5×50+10×100×50=75000。

因此是可以通过乘的次序不同来简化运算的，所以才有了此篇。

显然对上一个例子，我们在第二个矩阵之后断开，先分别算A1A2相乘的结果再将这结果与A3相乘的计算次数最少。

那么假设我们要算n个矩阵相乘也是一样的，需要选择在第i个矩阵后断开。然后对比在每个节点断开时的运算次序，选择最少的就是最优解。

由此动态规划的递推公式就出来了：

其中pi表示第i个矩阵的列，也即第i+1个矩阵的行。

图中的m数组即动态规划的dp数组。

从递推公式中可以看出算m[i,j]需要事先知道m[i,k]还有m[k+1,j],而无论是m[i,k]还是m[k+1,j]的长度都比m[i,j]短，所以计算整个m数组的顺序应该是从矩阵链长度短的推到长度长的，最后得到结果m[1][n]。