矩阵连乘python动态规划实现

矩阵连乘python动态规划实现

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]))