矩阵链最优的计算顺序python实现

矩阵链乘法（Matrix Chain Multiplication, MCM）是一个经典的计算机科学问题，目的是找到一种最有效的顺序来分块组合一系列矩阵相乘，以便最小化所需的乘法次数。最优解可通过动态规划算法求得。

Python实现矩阵链乘法的一般步骤如下：

1. 定义状态：设`dp[i][j]`表示将第i到j个矩阵按最优顺序连接后的最小乘法次数。
2. 状态转移方程：对于每个中间节点k (i <= k < j)，遍历所有可能的分割点l (i <= l < k)，计算`dp[i][j] = min(dp[i][l] + dp[l+1][j] + cost(matrix[i] * matrix[l+1] * ... * matrix[j]))`，其中`cost`是矩阵相乘的成本（假设都是平方阶），`matrix[l+1] * ... * matrix[j]`表示中间部分的子矩阵链。
3. 初始化：`dp[i][i] = 0`，因为单个矩阵不需要乘法。
4. 最终结果：`dp[1][n]`即为整个矩阵链的最小乘法次数，`result = [i, j]`记录了最优分割点。

下面是一个简单的Python代码示例：

def matrix_chain_order(p):
    n = len(p)
    if n == 1:
        return [0]

    dp = [[0 for _ in range(n)] for _ in range(n)]
    for L in range(2, n):
        for i in range(1, n - L + 1):
            j = i + L - 1
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])

    result = [n]
    while len(result) != 2:
        i, j = result.pop()
        k = dp[i][j] - dp[i][result[-1]] - dp[result[-1]+1][j]
        result.insert(0, k)

    return result

# 示例输入
matrices = [15, 20, 6, 7, 8, 10]
print("Optimal order:", matrix_chain_order(matrices))