核心：
if
i
>
=
j
i>=j
i>=j:
d
p
[
i
]
[
j
]
=
0
dp[i][j]=0
dp[i][j]=0
else:
d
p
[
j
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
+
p
[
i
−
1
]
∗
p
[
k
]
∗
p
[
j
]
dp[j][j]=max(dp[i][k]+dp[k+1][j]+p[i-1]*p[k] *p[j]
dp[j][j]=max(dp[i][k]+dp[k+1][j]+p[i−1]∗p[k]∗p[j] for k in (i,j)
)
)
)
class MatrixMultiplication:
def __init__(self, p):
self.p = p
self.dict = {}
self.ans = {}
def find(self, i, j):
if (i, j) in self.dict:
return self.dict[(i, j)]
elif i >= j:
if i == j:
self.ans[(i,i)] = chr(ord('A') + i-1)
pass
return int(0)
else:
ret = int(100000000)
for k in range(i, j):
if ret > self.find(i, k) + self.find(k + 1, j) + self.p[i - 1] * self.p[i] * self.p[j]:
self.ans[(i, j)] = "(" + self.ans[(i, k)] + ")" + "(" + self.ans[(k + 1, j)] + ")"
ret = self.find(i, k) + self.find(k + 1, j) + self.p[i - 1] * self.p[k] * self.p[j]
self.dict[(i, j)] = ret
return ret
if __name__ == '__main__':
p = [50, 10, 40, 30, 5, 20, 15]
s = MatrixMultiplication(p)
print(s.find(1, 6))
print(s.ans[(1, 6)])
print(s.dict)
print(s.p)
