矩阵链乘法问题python代码

以下是矩阵链乘法问题的Python代码：

import sys

def matrixChainOrder(p, n):
    m = [[0 for x in range(n)] for x in range(n)]
    s = [[0 for x in range(n)] for x in range(n)]

    for i in range(1, n):
        m[i][i] = 0

    for l in range(2, n):
        for i in range(1, n-l+1):
            j = i+l-1
            m[i][j] = sys.maxsize
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k

    return m[1][n-1], s

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

p = [30, 35, 15, 5, 10, 20, 25]
n = len(p)
minCost, s = matrixChainOrder(p, n)
print("Minimum number of multiplications is", minCost)
print("Optimal Parenthesization is: ", end="")
printParenthesis(s, 1, n-1)

这个算法使用了动态规划的思想，通过计算每个子问题的最优解来得到最终的结果。在这个代码中，`p` 是一个列表，包含了所有矩阵的大小。`n` 是矩阵的数量。最终的结果是最少需要的乘法次数和一个最优的括号化方案，这个方案通过 `printParenthesis` 函数打印出来。