矩阵连乘问题 python

矩阵连乘问题是指在计算多个矩阵相乘时，如何确定它们的相乘顺序，使得计算所需的总次数最少。

举个例子，我们有三个矩阵 A、B、C，它们的维度分别为 10*30、30*5、5*60。如果我们按照顺序 (A*B)*C 计算，则总次数为 10 * 30 * 5 + 10 * 5 * 60 = 4500，如果按照顺序 A*(B*C) 计算，则总次数为 30 * 5 * 60 + 10 * 30 * 60 = 27000。因此，我们应该选择第一种顺序。

在 Python 中，可以通过动态规划的方法解决矩阵连乘问题。具体实现可以参考以下代码：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0 for i in range(n)] for j in range(n)]
    s = [[0 for i in range(n)] for j in range(n)]
    for l in range(2, n+1):
        for i in range(n- 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

其中，p 是一个列表，表示每个矩阵的维度。例如，上面的例子可以表示为 p=[10, 30, 5, 60]。函数返回两个矩阵，m 表示最少需要的乘法次数，s 表示最优的相乘顺序。