'''Minimize multiplications multiplying a sequence of matrices.'''
def optSearchRec(count):
'''driver for plain recursive. count is list of counts in order.
The total number of comparisons is returned.'''
n = len(count)
leftSum = [0] * (n+1) # need extra index
for i in range(n): # leftSum[i] = count[0] + ... + count[i-1]
leftSum[i+1] = leftSum[i] + count[i]
return _optSearchRec(count, leftSum, 0, n-1)
def _optSearchRec(count, leftSum, low, high):
'''plain recursive. Returns total comparisons for tree from low to high.'''
if low > high:
return 0
best = 2**64
for root in range(low, high+1): # low .. high
cost = _optSearchRec(count, leftSum, low, root-1) + \
_optSearchRec(count, leftSum, root+1, high)
if cost < best:
best = cost
return best + leftSum[high+1] - leftSum[low]
print(optSearchRec([30, 65, 20, 10, 45]), 'total comparisons')