python编写·矩阵链乘法函数

在Python中，矩阵链乘法是一个经典的问题，通常用于演示递归算法和动态规划。矩阵链乘法是指计算一系列矩阵相乘的最短路径，每个矩阵代表一个操作，通过优化操作顺序可以减少总的乘法次数。这个问题可以用递归来解决。

下面是一个简单的函数示例，使用了动态规划的思想：

def matrix_chain_order(p):
    n = len(p)  # 数组长度，即矩阵的数量

    # 初始化一个二维数组，存储最优解
    dp = [[0 for _ in range(n)] for _ in range(n)]

    # 动态规划填充过程
    for L in range(2, n):  # 遍历所有可能的子问题规模
        for i in range(n - L + 1):  # 从第一个到最后L个元素
            j = i + L - 1  # 最后的元素索引
            # 找到当前子问题的最小代价
            dp[i][j] = float('inf')  # 初始值设为无穷大
            for k in range(i, j):  # 遍历中间节点
                # 计算当前最优解为两个子问题之和
                sub_cost = dp[i][k] + dp[k+1][j]
                if sub_cost < dp[i][j]:
                    dp[i][j] = sub_cost

    # 返回最后的最优解，即最短的操作序列
    return dp[0][-1], [i+1 for i in range(len(dp[0])-1) if dp[0][i+1] == dp[0][-1]]

# 示例输入，表示5个矩阵需要连乘
p = [1, 2, 3, 4, 5]
order, cost = matrix_chain_order(p)
print("最优操作顺序:", order)
print("总乘法次数:", cost, "次")