矩阵连乘问题代码手工图

以下是矩阵连乘问题的代码和手工图：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * n for _ in range(n)]
    s = [[0] * n for _ in range(n)]

    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 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("A" + str(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)

手工图如下：

A0  A1  A2  A3  A4  A5
|---|---|---|---|---|
   A0  A1  A2  A3  A4
    |---|---|---|---|
       A0  A1  A2  A3
        |---|---|---|
           A0  A1  A2
            |---|---|
               A0  A1
                |---|
                   A0

其中，`m` 是最小计算量的矩阵，`s` 记录了最优决策所分割的位置。`print_optimal_parens` 函数用于打印最优的加括号方式。以上代码和手工图都是针对矩阵 `A0`、`A1`、`A2`、`A3`、`A4`、`A5` 进行操作。