import numpy as np
"""
对于矩阵{A_0,A_1,... ...,A_n}
对应阶数{P_0,P_1,... ...,P_n,P_n+1}
它们的行列表达为 A_0 = P_0 * P_1
"""
def matrixChain(p, n=1, memo=None, seq=None):
#
size = len(p) - n # 子问题个数
if n == 1: # 长度为1的矩阵链，数乘次数为0
memo = np.zeros([size, size], dtype=int)
seq = np.zeros([size, size], dtype=int)
else: # 其他长度
for i in range(size): # 左边界
j = i + n - 1 # 右边界
for k in range(i, j): # 分界位置
t = memo[i, k] + memo[k + 1, j] + p[i] * p[k + 1] * p[j + 1]
if t < memo[i, j] or memo[i, j] == 0:
memo[i, j] = t
seq[i, j] = k
# 进入n+1
if n < len(p) - 1:
matrixChain(p, n + 1, memo, seq)
return memo, seq
def prtSeq(seq, i, j):
size = j-i+1
if size ==1:
return 'A%d'%i
else: # 至少有三个元素，才要考虑数乘顺序
k = seq[i,j] # 分界位置
res = ''
res += '('+ prtSeq(seq, i, k)
res += prtSeq(seq, k+1, j) + ')'
return res
n = eval(input('请输入矩阵个数：'))
p = eval(input('请输入矩阵尺寸：'))
m,seq = matrixChain(p)
res = prtSeq(seq,0,n-1)
print('最佳数乘次序：%s, 此时数乘次数：%d'%(res[1:-1], m[0,-1]))
