python矩阵连乘动态规划

矩阵连乘问题是指给定n个矩阵{A1, A2, ..., An}，其中Ai与Ai+1是可乘的，i=1,2,...,n-1。将它们相乘所需的标量乘法次数与加法次数有关，求出一种最优的计算次序，使得计算所需的总标量乘法次数最少。

动态规划是解决矩阵连乘问题的有效方法。其基本思想是将原问题分解为若干个子问题，先求解子问题，再由子问题的解得到原问题的解。具体来说，对于矩阵连乘问题，可以定义一个二维数组m[i][j]，表示从第i个矩阵到第j个矩阵的最小标量乘法次数。同时，还需要定义一个二维数组s[i][j]，表示从第i个矩阵到第j个矩阵的最优计算次序。则有以下状态转移方程：

m[i][j] = min{m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]}，其中i<=k<j

s[i][j] = k，其中i<=k<j且m[i][j] = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]

其中p[i]表示第i个矩阵的行数，第i+1个矩阵的列数。

根据上述状态转移方程，可以使用动态规划算法求解矩阵连乘问题。具体实现过程如下：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * n for i in range(n)]
    s = [[0] * n for i in range(n)]
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
    return m, s

def print_optimal_parens(s, i, j):
    if i == j:
        print("A" + str(i), end="")
    else:
        print("(", end="")
        print_optimal_parens(s, i, s[i][j])
        print_optimal_parens(s, s[i][j]+1, j)
        print(")", end="")

p = [30, 35, 15, 5, 10, 20, 25]
m, s = matrix_chain_order(p)
print_optimal_parens(s, 0, len(p)-2)

上述代码中，matrix_chain_order函数用于计算最小标量乘法次数和最优计算次序，print_optimal_parens函数用于输出最优计算次序。对于给定的矩阵大小p=[30, 35, 15, 5, 10, 20, 25]，输出结果为((A0(A1A2))((A3A4)A5))，表示最优计算次序为(A1A2)、(A3A4)和((A1A2)(A3A4))先相乘，然后再与A0、A5相乘。