import sys
def init(c, n):
for i in range(n):
temp = [0] * n
c.append(temp)
def matrix_chain(c, matrix, i, j):
if i == j:
return 0
elif c[i][j] != 0:
return c[i][j]
min_count = sys.maxsize
for k in range(i + 1, j + 1):
count = matrix_chain(c, matrix, i, k - 1) + matrix_chain(c,
matrix, k, j) + matrix[k] * matrix[j + 1] * matrix[i]
min_count = min(count, min_count)
c[i][j] = min_count
return min_count
matrix = [30, 35, 15, 5, 10, 20, 25]
c = []
n = len(matrix)
init(c, n)
i = 1
j = 6
res = matrix_chain(c, matrix, i - 1, j - 1)
print(res)