矩阵连乘问题的动态规划代码python

矩阵连乘问题，也称为矩形矩阵链乘法优化，是一个经典的问题，可以使用动态规划算法来解决。动态规划的主要目标是找到一种最优的方式来计算一系列矩阵相乘的最小代价。给定一组矩阵A1, A2, ..., An，我们要找到一种顺序来分解这些矩阵，使得总的乘法次数最少。

Python代码实现如下：

def matrix_chain_order(p):
    n = len(p)
    # 初始化一个二维数组dp，其中dp[i][j]表示将p[i:j+1]这一串矩阵按某种顺序连接所需要的最少乘法次数
    dp = [[0 for _ in range(n)] for _ in range(n)]
    
    # 动态规划的基本思路：遍历所有长度为k（1到n-1）的子序列，计算每种排列方式的成本
    for l in range(2, n):
        for i in range(n - l + 1):
            j = i + l - 1
            dp[i][j] = float('inf')  # 初始值设为无穷大
            for k in range(i, j):
                temp_cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                if dp[i][j] > temp_cost:
                    dp[i][j] = temp_cost

    # 最终结果会存储在dp[0][n-1]中，返回这个值即可
    return dp[0][n - 1]

# 示例输入：p = [15, 20, 6, 9, 4, 2]
p = [1, 5, 7, 2, 3, 4]  # 这里是一个简化版本，假设每个数字代表对应矩阵的维度
result = matrix_chain_order(p)
print(f"最优的矩阵连乘顺序需要的乘法次数为: {result}")