[Solved] Python max benefit [closed]

by


The number of possible routes through a tree is 2**rows. The number of possible routes to a given node is given by the binomial expansion. You can grow the possible routes from the head of the tree quite simply, at each node there are only two possible next moves, their indexes in the list are either the same as the current position or one more.

A simple way to solve the problem is to generate all possible paths for a given number of rows. create_paths() does this, returning all possible routes through the tree. Function max_cost() uses this to evaluate all routes against the cost tree, returning the value of the most expensive route. I leave it to you to get the actual route out (not very hard..) 🙂

L_0 = [[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]]
L_1 = [[11], [7,32], [14,14,14], [0,1,2,3], [5,99,1,2,7],
       [0,25,9,45, 54,1], [99,88,77,66,55,44,33]]

def create_paths(rows):
    new_paths = []
    paths = [[0]]
    for row in xrange(rows):
        for path in paths:
            new_paths.append(path+[path[-1]])
            new_paths.append(path+[path[-1]+1])
        paths = new_paths
        new_paths = []
    return paths

def max_cost(tree):
    costs = []
    paths = create_paths(len(tree)-1)
    for path in paths:
        costs.append(sum([tree[i][j] for i, j in enumerate(path)]))
    return max(costs)

print max_cost(L_0)
print max_cost(L_1)

#output:
30
270

solved Python max benefit [closed]