36 lines
961 B
Python
36 lines
961 B
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(n - L + 1):
|
|
j = i + L - 1
|
|
m[i][j] = 10**18
|
|
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 build_parenthesization(s, i, j, names):
|
|
if i == j:
|
|
return names[i]
|
|
k = s[i][j]
|
|
return (
|
|
"("
|
|
+ build_parenthesization(s, i, k, names)
|
|
+ build_parenthesization(s, k + 1, j, names)
|
|
+ ")"
|
|
)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
p = [30, 35, 15, 5, 10, 20, 25]
|
|
names = ["A", "B", "C", "D", "E", "F"][: len(p) - 1]
|
|
m, s = matrix_chain_order(p)
|
|
expr = build_parenthesization(s, 0, len(p) - 2, names)
|
|
print(m[0][len(p) - 2])
|
|
print(expr)
|