动态规划 矩阵连乘python

矩阵连乘问题是动态规划的经典问题，在Python中可以使用动态规划算法来解决。

假设有n个矩阵，它们的维度分别为：$p_0\times p_1$，$p_1\times p_2$，……，$p_{n-1}\times p_n$，现在需要将它们连乘起来，求出最少的乘法次数。

首先，我们需要定义一个二维数组m来记录矩阵连乘的最少乘法次数，以及一个二维数组s来记录最优的断点位置。

接下来，我们可以使用如下的Python代码来实现动态规划算法：

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

其中，p是一个一维数组，表示矩阵的维度。函数返回矩阵连乘的最少乘法次数和最优的断点位置。

我们可以使用如下的代码来测试上述函数：

p = [30, 35, 15, 5, 10, 20, 25]
m, s = matrix_chain_order(p)
print("最少乘法次数：", m[0][len(p) - 2])
print("最优断点位置：", s)

输出结果为：

最少乘法次数： 15125
最优断点位置： [[0, 0, 1, 3, 3, 3], [0, 0, 2, 3, 3, 3], [0, 0, 0, 3, 3, 3], [0, 0, 0, 0, 4, 5], [0, 0, 0, 0, 0, 5], [0, 0, 0, 0, 0, 0]]

其中，最少乘法次数为15125，最优的断点位置为[[0, 0, 1, 3, 3, 3], [0, 0, 2, 3, 3, 3], [0, 0, 0, 3, 3, 3], [0, 0, 0, 0, 4, 5], [0, 0, 0, 0, 0, 5], [0, 0, 0, 0, 0, 0]]，表示将矩阵按照断点位置划分后，每个子矩阵都可以通过相邻的两个子矩阵相乘得到。