'''Minimize multiplications multiplying a sequence of matrices.
What is the order of this version?'''
def multCost1(dims):
'''Recursive, bottom up, pick next location in list to multiply.'''
n = len(dims)
if n < 3:
return 0
best = 2**64
for i in range (1, n-1):
oneMult = dims[i-1]*dims[i]*dims[i+1]
nextDims = dims[:] # copies
nextDims[i:i+1] = [] # removes element i
cost = oneMult + multCost1(nextDims)
if cost < best:
best = cost
return best
print(multCost1([30, 1, 40, 10, 25]))