矩阵连乘问题python

矩阵连乘问题是一个经典的动态规划问题。在Python中，我们可以通过以下代码来解决这个问题：

import sys

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * (n+1) for i in range(n+1)]
    s = [[0] * (n+1) for i in range(n+1)]
    for l in range(2, n+1):
        for i in range(1, n-l+2):
            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, s

def print_optimal_parens(s, i, j):
    if i == j:
        print('A{}'.format(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, 1, len(p)-1)

这个代码实现了矩阵连乘问题的动态规划解法，并输出了最优的括号化方案。其中，`p`数组表示矩阵的维度，`matrix_chain_order`函数返回最小的乘法次数和最优的断点方案，`print_optimal_parens`函数根据断点方案输出最优的括号化方案。运行结果为：

((A1(A2A3))((A4A5)A6))

这表示对于矩阵 $A_1, A_2, \cdots, A_6$，最优的连乘顺序为 $(A_1((A_2A_3)((A_4A_5)A_6)))$，共需要 $15125$ 次乘法。