DP on Trees

The Idea

On a tree there is no left-to-right order to sweep, so the recursion carries the state instead. Each node returns two numbers: the best total if it is taken, and the best if it is skipped. A parent that takes itself may only add its children's skip values. The tree is walked once, bottom-up.

Real-World Example

An org chart planning a surprise party where nobody may be invited alongside their direct manager. Each team lead reports two totals upward — the best party including them and the best excluding them — and the CEO picks the larger of their own pair.

The Code

tree = {"a": ["b", "c"], "b": ["d", "e"], "c": [], "d": [], "e": []}
loot = {"a": 3, "b": 4, "c": 5, "d": 1, "e": 1}

def best(node):
    take, skip = loot[node], 0
    for kid in tree[node]:
        kid_take, kid_skip = best(kid)
        take += kid_skip                    # taking here forbids the children
        skip += max(kid_take, kid_skip)     # skipping here frees them
    return take, skip

print(best("b"))         # (4, 2)
print(max(best("a")))    # 9 — skip a, take b and c

tree = {"r": ["x"], "x": []}
loot = {"r": 2, "x": 5}

def best(node):
  take, skip = loot[node], 0
  for kid in tree[node]:
      kid_take, kid_skip = best(kid)
      take += kid_skip
      skip += max(kid_take, kid_skip)
  return take, skip

print(best("r"))