已知矩陣Am*n和Bn*p相乘的時(shí)間復(fù)雜度為O(mnp)。矩陣相乘滿足結(jié)合律，如三個(gè)矩陣A、B、C相乘的順序可以是(A*B)*C也可以是A*(B*C)。不同的相乘順序所需進(jìn)行的乘法次數(shù)可能有很大的差別。因此確定n個(gè)矩陣相乘的最優(yōu)計(jì)算順序是一個(gè)非常重要的問(wèn)題。已知確定n個(gè)矩陣A,A2、、、、、、An相乘的計(jì)算順序具有最優(yōu)子結(jié)構(gòu)，即A1A2、、、、、、An的最優(yōu)計(jì)算順序包含其子問(wèn)題A1A2、、、、、、Ak和Ak+1Ak+2……An（l＜=k＜n）的最優(yōu)計(jì)算順序。
可以列出其遞歸式為：

其中，Ai的維度為pi-1*pim[i，j]表示AiAi+1……Aj最優(yōu)計(jì)算順序的相乘次數(shù)。
先采用自底向上的方法求n個(gè)矩陣相乘的最優(yōu)計(jì)算順序。則求解該問(wèn)題的算法設(shè)計(jì)策
略為（ 1）。算法的時(shí)間復(fù)雜度為（2 ），空間復(fù)雜度為（ 3）。
給定一個(gè)實(shí)例，（POPi……P5）=（20,15,4,10,20,25）,最優(yōu)計(jì)算順序?yàn)椋?4）。
（1）A、分治法
B、動(dòng)態(tài)規(guī)劃法
C、貪心法
D、回溯法
（2）A、O(n2)
B、O(n2lgn)
C、O(n3)
D、O(2n)
（3）A、O(n2)
B、O(n2lgn)
C、O(n3)
D、O(2n)
（4）A、(((A1*A2)*A3)*A4)*A5
B、A1*(A2*(A3*(A4*A5)))
C、((A1*A2)*A3)*(A4*A5)
D、(A1*A2)*((A3*A4)*A5)