Skip to content

Instantly share code, notes, and snippets.

@dobrokot
Created May 11, 2012 09:31
Show Gist options
  • Save dobrokot/2658635 to your computer and use it in GitHub Desktop.
Save dobrokot/2658635 to your computer and use it in GitHub Desktop.
minimal tree cost built from list
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment