document.write('该问题实际上并不是执行乘法，而只是决定以哪个顺序执行乘法。由于矩阵乘法是关联的，所以我
们有很多选择来进行矩阵链的乘法运算。换句话说，无论我们采用哪种方法来执行乘法，结果将是
一样的。例如，如果我们有四个矩阵A、B、C和D，可以有如下几种执行乘法的方法：
(ABC) D=(AB) (CD) =A (BCD)=…
虽然这些方法的计算结果相同。但是，不同的方法需要执行乘法的次数是不相同的，因此效率也
是不相同的。例如，假设A是10×30矩阵，B是30×5矩阵，C是5×60矩阵。那么，(AB)C的执行乘
法运算的次数为(10×30×5)+(10×5×60)=1500+3000=4500次。
A (BC)的执行乘法运算的次数为(30×5×60)+(10×30×60)=9000+18000=27000次。
显然，第一种方法需要执行更少的乘法运算，因此效率更高。
对于本题中示例而言，执行乘法运算的次数最少的方法如下：
(A (BC)) D的执行乘法运算的次数为20*30*10+40*20*10+40*10*30。
方法一：递归法
最简单的方法就是在所有可能的位置放置括号，计算每个放置的成本并返回最小值。在大小为n的
矩阵链中，我们可以以n-1种方式放置第一组括号。例如，如果给定的链是4个矩阵。(A) (BCD)，
(AB) (CD)和(ABC) (D)中，有三种方式放置第一组括号。每个括号内的矩阵链可以被看作较小的子
问题。因此，可以使用递归方便地求解。递归的实现代码如下：
def MatrixChainOrder(p,i,j):
if i==j:
return 0
mins=2**32
"""
通过把括号放在第一个不同的地方来获取最小的代价
每个括号内可以递归地使用相同的方法来计算
"""
k=i
while k＜j:
count=MatrixChainOrder(p,i,k)+\\
MatrixChainOrder(p,k+1,j)+\\
p[i-1]*p[k]*p[j]
if count＜mins:
mins=count
k+=1
return mins
if __name__=="__main__":
arr=[1,5,2,4,6]
n=len(arr)
print "最少的乘法次数为"+str(MatrixChainOrder(arr,1,n-1))
程序的运行结果为：
最少的乘法次数为42
这种方法的时间复杂度是指数级的。可以注意到，这种算法会对一些子问题进行重复的计算。例
如在计算(A) (BCD)这种方案的时候会计算C*D的代价，而在计算(AB) (CD)这种方案的时候又会重复
计算C*D的代价。显然子问题是有重叠的，对于这种问题，通常可以用动态规划的方法来降低时间
复杂度。
方法二：动态规划
典型的动态规划的方法是使用自下而上的方式来构造临时数组来保存子问题的中间结果，从而可
以避免大量重复的计算。实现代码如下：
def MatrixChainOrder(p,n):
cost=[([None]*n) for i in range(n)]
i=1
white i＜n:
cost[i][i]=0
i+=1
cLen=2
while cLen＜n:
i=1
while i＜n-cLen+1:
j=i+cLen-1
cost[i][j]=2**31
k=i
while k＜=j-1:
q=cost[i][k]+cost[k+1][j]+[i-1]*p[k]*p[j]
if (q＜cost[i][j]):
cost[i][j]=q
k+=1
i+=1
cLen+=1
return cost[1][n-1]
if __name__=="__main__":
arr=[1,5,2,4,6]
n=len(arr)
print "最少的乘法次数为 "+str(MatrixChainOrder(arr,n))
算法性能分析：
这种方法的时间复杂度为O(n3)，空间复杂度为O(n2)。
');