python矩阵连乘_python动态规划解决矩阵连乘

矩阵连乘问题就是给定一系列矩阵，求它们相乘的最少次数。这个问题可以使用动态规划来解决。

我们可以定义一个二维数组m[i][j]来表示矩阵Ai到Aj的最少次数，其中i<=j。对于任意的i和j，m[i][j]的值可以通过以下递推式计算出来：

m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}，其中i<=k<j，p[i-1]表示第i个矩阵的行数，p[j]表示第j个矩阵的列数。

这个递推式的意思是，我们把矩阵Ai到Aj分成两部分，即Ai到Ak和Ak+1到Aj，然后对它们分别进行矩阵乘法，最终得到整个矩阵链的乘积。我们需要遍历所有可能的k，选择乘积最小的那个。

最终的答案就是m[1][n-1]，其中n表示矩阵的个数。

下面是Python代码实现：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[float('inf')] * n for _ in range(n)]
    s = [[0] * n for _ in range(n)]
    for i in range(n):
        m[i][i] = 0
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            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("A{}".format(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(m[0][len(p)-2])
print_optimal_parens(s, 0, len(p)-2)

这个代码的输出结果是：

15125
((A1(A2A3))((A4A5)A6))

其中15125表示最少的矩阵乘法次数，((A1(A2A3))((A4A5)A6))表示矩阵相乘的最优顺序。