用二维数组实现矩阵连乘输出最优断点数

矩阵连乘问题是一个经典的动态规划问题，可以使用二维数组实现。假设有n个矩阵，它们的维度分别为d[0]×d[1]，d[1]×d[2]，...，d[n-2]×d[n-1]，则这n个矩阵相乘的总代价为：

M[i,j] = 0, i = j
M[i,j] = min{M[i,k]+M[k+1,j]+d[i-1]×d[k]×d[j]}，i ≤ k < j

其中，M[i,j]表示从第i个矩阵到第j个矩阵相乘的最小代价，d数组表示每个矩阵的维度。上式中的i、j、k都是矩阵的下标，k表示断点位置。因此，我们可以使用一个二维数组M来记录所有的M[i,j]值，再使用一个二维数组S来记录断点位置，即对于每个M[i,j]，S[i][j]记录了使得M[i,j]最小的断点位置k。

下面是使用二维数组实现矩阵连乘问题的代码：

def matrix_chain_order(dims):
    n = len(dims) - 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(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] + dims[i]*dims[k+1]*dims[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="")

其中，dims是一个包含n+1个元素的列表，表示n个矩阵的维度。函数matrix_chain_order返回两个二维数组m和s，分别表示所有M[i,j]值和断点位置。函数print_optimal_parens用于输出最优的断点数，它接受三个参数：数组s、矩阵下标i、矩阵下标j。