矩阵的乘法
矩阵的概念来自线性代数
矩阵乘法:只有当左边矩阵的列数等于右边矩阵的行数
时,它们才可以相乘。
结果为前一个矩阵的行元素×后一个矩阵的列元素
矩阵相乘的最小相乘次数产生的原因
乘积矩阵(相乘的结果)的行数等于左边矩阵的行数乘积
矩阵的行数等于右边矩阵的列数
实例: 2x 3的矩阵乘以3x 4的矩阵得2 x 4的矩阵
矩阵连乘，简单来说是多个矩阵进行相乘。
但不同的运算次序，其计算量也大概率不同。
如:假设A为10 * 100的矩阵，B为100* 5的矩阵，C为5 * 50的矩阵，
那么矩阵连乘有两种情况:
1、(A* B)*C-共要乘10*100*5+10*5*50 = 7500次
2、A*(B*C)一共要乘100*5*50+10*100 * 50 = 75000次
同样的例子：
第一种(A* B)*C
{( 2:3 )*( 3:2 )}*(2:4 ) -> 2x3x2 = 12
(2:2)*(2:4 ) -> 2x2x4=16.
12 + 16 = 28
第二种
( 2:3 )*{( 3:2 )*(2:4 )} -> 3x2x4 = 24
(2:3)*(3:4 ) -> 2x3x4=24.
24 + 24 = 48
动态规划思路
求最小的矩阵连乘，相当于，在每一个子问题中找到最小的连乘数
适用动态规划的思想
开始时看
当只有两个矩阵时
很显然，只有一种结果
就是从中间进行断开
三个矩阵的时候
我们应该分开计算前两个和后两个的解
之后进行比较 ，获得子问题的最优结构
计算前两个和后两个
获得两个子问题解后后与剩下的计算相比较就能得到： 三个矩阵情况下的最优解
四个矩阵的时候
很显然我们应该和三个的情况一样
从下往上进行计算最优解
1：计算第三层中，每两个相邻向量的解(因为相邻向量的前一个行数和后一个列数相同才能计算)；
2：计算第二层中的，三个相邻组合的最优解，同上文；
设k为隔板，k = 2 时，表示（A1*A2）* A3 为最优解;
k 的取值范围是 （i , j-)
在第二层的对比中，我们重复利用了第三层的计算值
因此我们可以将已经计算过的值放入表中，减少重复的计算
3：计算第一层，很显然就是将第二层的两个最优解与剩下的相乘即可
计算这六个矩阵
我们可以发现我们是将这些矩阵分开计算
先是两两一组，之后是三个一组，以此类推到五个一组，最后得出6个一组的最小值
将每一次的计算结构放入表中减少重复的计算
标签：连乘,行数,矩阵,相乘,计算,100 From： https://www.cnblogs.com/kuailest/p/16811749.html