已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别
已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵A1A2.....An相乘的计算顺序具有最优子结构，即A1A2......An的最优计算顺序包含其子问题A1A2.....Ak和Ak+1Ak+2......An (1<k<n) 的最优计算顺序。可以列出其递归式为:
其中，Ai的维度为pi-1 *Pi，m[i,j]表示AiAi+1.....Aj最优计算顺序的相乘次数。先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策略为( )。算法的时间复杂度为( )，空间复杂度为( )。给定一个实例，(p0p1......p5)= (20,15,4,10,20,25) ，最优计算顺序为( )（2019年软件设计师上半年）
A.分治法
B.动态规划法
C.贪心法
D.回溯法
A.O(n²)
B.O(n²lgn)
C.O(n³)
D.O(2^n)
A.O(n²)
B.O(n²lgn)
C.O(n³)
D.O(2^n)
A. （((A1 *A2)*A3)*A4)*A5
B. A¡*(A2*(A3*(A4*A5)))
C. ((A¡*A2)*A3)* (A4*A5)
D. (A¡*A2) *((A3*A4)*A5)
参考答案：B C A D
参考解析：