用动态规划法实现矩阵连乘实验结论

矩阵连乘问题是指给定n个矩阵A1,A2,A3,...,An，求它们相乘的最小代价。矩阵相乘的代价可以用乘法次数来表示，比如A1是p1 * q1的矩阵，A2是p2 * q2的矩阵，那么A1 * A2的代价就是p1 * q2 * q1。

动态规划的思路是将原问题分解为若干个子问题，先求解子问题，再由子问题的解得到原问题的解。在矩阵连乘问题中，我们可以将相乘的矩阵分为两部分，分别计算左边和右边矩阵相乘的最小代价，然后将左右两部分相加得到最终的最小代价。

具体实现的步骤如下：

1. 定义一个二维数组m来保存计算出来的最小代价，m[i][j]表示Ai到Aj相乘的最小代价。

2. 定义一个二维数组s来保存每个最优解对应的断点位置，s[i][j]表示Ai到Aj相乘的最优断点位置。

3. 对于每个长度为l的子问题，从i=1到n-l+1，计算m[i][i+l-1]和s[i][i+l-1]的值。

4. 最终的最小代价就是m[1][n]，最优解的断点位置可以通过s[1][n]来递归求解。

下面是用Python实现矩阵连乘的动态规划算法：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * n for _ in range(n)]
    s = [[0] * n for _ in range(n)]
    for l in range(2, n + 1):
        for i in range(0, 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] * 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(f"A{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_optimal_parens(s, 0, len(p) - 2)
print(f"\nMinimum cost: {m[0][-1]}")

这段代码用了两个函数，`matrix_chain_order`计算最小代价和最优解的断点位置，`print_optimal_parens`通过递归打印最优解。对于输入`p = [30, 35, 15, 5, 10, 20, 25]`，输出结果如下：

((A0(A1A2))((A3A4)A5))
Minimum cost: 15125

这表示最小代价为15125，最优解是将A0到A5分成两部分，分别是(A0(A1A2))和((A3A4)A5)。