'''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')