用动态规划法实现矩阵连乘代码

好的，以下是使用动态规划法实现矩阵连乘的代码：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * n for _ in range(n)]
    s = [[0] * n for _ 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(f"A{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)

该代码以矩阵链乘的维度列表 p 作为输入，其中 p[i] 和 p[i+1] 表示矩阵 Ai 和 Ai+1 的行数和列数。该代码使用动态规划法计算矩阵连乘的最小代价，并使用 s 数组记录最优括号化方案。print_optimal_parens 函数输出最优括号化方案。在上面的示例中，输出为 ((A0(A1A2))((A3A4)A5))。