Advanced DP: Trees & Bitmask — Algorithms Course

What you'll learn

DP isn't confined to arrays and grids. Two advanced settings round out the phase: tree DP, where subproblems are subtrees, and bitmask DP, where the state is a set encoded in the bits of an integer.

By the end you'll be able to:

Run a DP over the nodes of a tree
Encode a subset as a bitmask and DP over subsets
Solve the travelling salesman problem with Held-Karp

DP on trees

On a tree, a node's answer depends on its children's answers — perfect for a post-order DP. Take maximum independent set (a "house robber" on a tree): you can't pick a node and its child. For each node, compute two values: the best if you take it (so children are skipped) and the best if you skip it (children choose freely).

Tree DP in code

Language

rob_tree.py

def rob_tree(node):
    # returns (best if node NOT taken, best if node taken)
    if node is None:
        return (0, 0)
    l = rob_tree(node.left)
    r = rob_tree(node.right)
    taken = node.val + l[0] + r[0]        # children must be skipped
    skipped = max(l) + max(r)             # children free to choose
    return (skipped, taken)

def solve(root):
    return max(rob_tree(root))

Note

The pattern — return a small tuple of "states" per node and combine children in the parent — covers a huge range: subtree sizes, diameters, weighted matchings, and coloring all follow it. One post-order pass is O(n).

Bitmask DP

When n is small (say ≤ 20), you can make the DP state a subset of the items, stored as the bits of an integer. Bit i set means "item i is in the set":

A subset as a bitmask

mask 1011 = {A, B, D} chosen, C left out

With this encoding, dp[mask] (or dp[mask][…]) ranges over all 2ⁿ subsets, and transitions flip bits on or off. Union is |, intersection &, and "is item i in the set?" is mask & (1 << i).

Bitmask TSP (Held-Karp)

The travelling salesman problem — the shortest tour visiting every city once — is NP-hard, so brute force is O(n!). Bitmask DP cuts it to O(2ⁿ · n²): let dp[mask][i] be the shortest path that visits exactly the cities in mask and ends at city i. Extend by adding one new city j: dp[mask | (1<<j)][j] = min(dp[mask][i] + dist[i][j]).

Key idea

O(2ⁿ · n²) is still exponential — but for n = 18 it's about 85 million operations instead of 18! ≈ 6×10¹⁵. Bitmask DP makes small instances of hard problems genuinely solvable.

Recap & quick check

Key takeaways

Tree DP computes each node's answer from its children in one post-order pass — O(n).
Return a small tuple of states per node (e.g. taken vs skipped) and combine in the parent.
Bitmask DP encodes a subset in the bits of an integer for n ≤ ~20.
Set ops: union |, intersection &, membership mask & (1<<i).
Held-Karp solves TSP in O(2ⁿ·n²) — exponential, but far better than O(n!).

Quick check

1. In tree DP for maximum independent set, why return two values per node?

2. How is a subset represented in bitmask DP?

3. What is the complexity of Held-Karp TSP?

4. How do you test if item i is in a bitmask?

That completes dynamic programming. Next we explore solution spaces directly, building and pruning. Next up: Module 21 — Backtracking.