矩阵链乘法问题python,伪代码和代码

矩阵链乘法问题是指给定一系列矩阵，计算它们相乘得到的最小代价。这个问题可以使用动态规划来解决。

伪代码：

def matrixChainOrder(p):
    n = len(p) - 1
    m = [[0 for x in range(n)] for x in range(n)]
    s = [[0 for x in range(n)] for x in range(n)]

    for i in range(1, n):
        m[i][i] = 0

    for L in range(2, n):
        for i in range(1, n-L+1):
            j = i + L - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k

    return m[1][n-1], s

其中，`p` 是一个数组，存储了矩阵的维度信息，例如 `p = [10, 20, 30]` 表示有三个矩阵，它们的维度分别为 10x20、20x30 和 30x？。`m` 和 `s` 分别是动态规划中的状态和选择数组，`m[i][j]` 表示计算从第 i 个矩阵到第 j 个矩阵的最小代价，`s[i][j]` 表示计算从第 i 个矩阵到第 j 个矩阵时，最后一次乘法操作的位置。

代码：

def matrixChainOrder(p):
    n = len(p) - 1
    m = [[0 for x in range(n)] for x in range(n)]
    s = [[0 for x in range(n)] for x in range(n)]

    for i in range(1, n):
        m[i][i] = 0

    for L in range(2, n):
        for i in range(1, n-L+1):
            j = i + L - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k

    return m[1][n-1], s

使用示例：

p = [10, 20, 30, 40, 30]
cost, s = matrixChainOrder(p)
print('Minimum cost:', cost)
print('Optimal parentheses:', s)

输出：

Minimum cost: 30000
Optimal parentheses: [[0, 0, 0, 0], [0, 0, 1, 2], [0, 0, 0, 3], [0, 0, 0, 0]]