矩阵链乘法问题 python

矩阵链乘法问题是指给定一系列的矩阵，求解它们相乘的最小代价。在这个问题中，我们需要考虑矩阵相乘的顺序对最终代价的影响。

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

import sys

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] = sys.maxsize
            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` 是一个包含矩阵维度的列表，例如 `[30, 35, 15, 5, 10, 20, 25]` 表示两个矩阵的维度分别为 30x35 和 35x15，以此类推。`matrix_chain_order` 函数返回两个矩阵，`m` 存储矩阵相乘的最小代价，`s` 存储最优的相乘顺序。`print_optimal_parens` 函数根据 `s` 打印出最优的相乘顺序。