forked from Gitlink/forgeplus
36 lines
846 B
Python
36 lines
846 B
Python
p = [30, 35, 15, 5, 10, 20, 25]
|
|
N = len(p) - 1
|
|
m = [[0 for _ in range(0, N)] for _ in range(0, N)]
|
|
s = [[0 for _ in range(0, N)] for _ in range(0, N)]
|
|
|
|
|
|
def matrix(n):
|
|
for r in range(2, n):
|
|
for i in range(1, n - r + 1):
|
|
j = i + r - 1
|
|
m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]
|
|
s[i][j] = i
|
|
for k in range(i + 1, j):
|
|
t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
|
|
if t < m[i][j]:
|
|
m[i][j] = t
|
|
s[i][j] = k
|
|
|
|
|
|
def cout(i, j):
|
|
if i == j:
|
|
print('A[', i, ']', end=' ')
|
|
return
|
|
print('(', end=' ')
|
|
cout(i, s[i][j])
|
|
cout(s[i][j] + 1, j) # 递归1到s[1][j]
|
|
print(')', end=' ')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
matrix(N)
|
|
for i in m[1:]:
|
|
print(i[1:])
|
|
cout(1, N - 1)
|
|
|