矩阵链乘法问题用python实现

矩阵链乘法问题可以使用动态规划来解决，下面是Python代码实现：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[float('inf') for _ in range(n)] for _ in range(n)]
    s = [[-1 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        m[i][i] = 0
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            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{}'.format(i+1), 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('Minimum number of scalar multiplications:', m[0][-1])
print('Optimal parenthesization:', end=' ')
print_optimal_parens(s, 0, len(p)-2)

其中，`matrix_chain_order(p)`函数计算出每个子问题的最优解和最优决策，`print_optimal_parens(s, i, j)`函数输出最优的括号方案。

以`p = [30, 35, 15, 5, 10, 20, 25]`为例，输出结果为：

Minimum number of scalar multiplications: 15125
Optimal parenthesization: ((A1(A2A3))((A4A5)A6))

说明最优的括号方案是`((A1(A2A3))((A4A5)A6))`，并且最少需要进行15125次标量乘法运算。