Lesson 32.3 · Advanced DP
DP on Trees
Each subtree returns a small tuple, such as (best if this node is used, best if not), and the parent combines its children's tuples.
12 min
Think of it like this
A company organising a party where no one attends with their direct manager. Each team lead reports two numbers upward: the best fun if they attend, and the best if they don't.
1.Post-order with tuples
House Robber III: a node returns {rob, skip}. rob = value + skip(left) + skip(right); skip = max(left) + max(right). The answer is the max at the root.
Binary Tree Cameras: each node returns one of three states (needs coverage, has a camera, covered without camera). Leaves report "needs coverage", forcing a camera at their parent: a greedy that tree DP proves correct.
root = [3, 2, 3, null, 3, null, 1]Step 1/3Leaves: rob = value, skip = 0.
Remember
- Return a tuple per subtree.
- Combine in post-order.
- O(n) total.
Common mistakes
- Memoising on the node with a HashMap when a tuple return does it without extra memory.