minimal tree cost built from list

tree_cost.py

# minimal tree cost built from list, problem from http://antilamer.livejournal.com/431230.html
# cost of tree is sum(depth(i)*value(i))

list = [1,2,3,4,5,7,6,5,4,3,2,10000]

n = len(list)

#table from (start, length) to (cost, x-sum, root) for best tree on segment (start, length)
table_start_l = [[(0,0,-1000)]*(n-start+1) for start in xrange(n+1)]

for l in xrange(1, n+1):
    for start in xrange(0, n-l+1):
    
        best_cost = 1e100
        best_sum = None
        best_root = None
    
        for root in xrange(start, start+l):
            l_cost, l_sum, l_root = table_start_l[start][root-start]
            r_cost, r_sum, r_root = table_start_l[root+1][l-(root-start+1)]
            
            cost = l_cost + r_cost + l_sum + r_sum
            if cost < best_cost:
                best_cost = cost
                best_sum = l_sum + r_sum + list[root]
                best_root = root
                
        table_start_l[start][l] = (best_cost, best_sum, best_root)
        

def print_tree(start, l):
    import sys
    if l == 0:
        return 
    _,_,root = table_start_l[start][l]
    sys.stdout.write('(')
    left = print_tree(start, root-start)
    print ',', list[root], ',',
    right = print_tree(root+1, l - (root-start+1))
    sys.stdout.write(')')
    
        
print_tree(0, n)