两个矩阵 Am*n 和 Bn*p 相乘，用基本的方法进行，则需要的乘法次数为 m*n*p 。多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定 Mi ， M(i+1) ， … ， Mj 多个矩阵连乘的最优顺序，即所需要的乘法次数最少。最少乘法次数用 m[i,j] 表示，其递归式定义为：
其中 i 、 j 和 k 为矩阵下标，矩阵序列中 Mi 的维度为（ pi-1 ） *pi 采用自底向上的方法实现该算法来确定 n 个矩阵相乘的顺序，其时间复杂度为（ ）
- A.O（n2）
- B.O（n2lgn）
- C.O（n3）
- D.O（n3lgn）
正确答案及解析
正确答案
C
解析
四个矩阵分别为：
2*6 6*3
