python矩阵连乘

矩阵连乘问题是指给定n个矩阵A1，A2，…，An，求其相乘的最小代价。假设矩阵Ai的维数为pi-1 × pi（i=1,2,…,n）。

可以采用动态规划的方法来解决该问题。定义一个二维数组m[i][j]表示从第i个矩阵到第j个矩阵相乘的最小代价。则有以下状态转移方程：

m[i][j] = min(m[i][k] + m[k+1][j] + pi-1 * pk * pj) (i <= k < j)

其中，k是i和j之间的分割点，pi-1 * pk * pj是两个矩阵相乘的代价。

代码如下：

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 + 2):
            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{}'.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, 0, len(p) - 2)

其中，p是一个列表，表示矩阵的维数。运行结果为：((A0(A1A2))(A3(A4A5)))。