Dynamic programming 0/49

Lesson 3 of 3 Advanced

Tree DP: combining rooted subtree states

Solve a tree problem from its subtrees: return the states a parent needs about each child, combine finished children, and reroot with a second pass.

4,557 words · 21 min read

Part 1 of 10 Tree DP

Tree DP

Tree DP is dynamic programming on a rooted tree. The subtree of a vertex vv is vv together with everything below it: its children, their children, and so on down to the leaves. Each state describes one subtree, and the transition builds a subtree’s answer from the answers for its root’s children, whose subtrees are smaller. House Robber III is a first example.

Difficulty tier:Normal

Houses form a binary tree, and each node holds some money. A thief may rob any set of houses, except that robbing two houses joined directly by an edge sets off the alarm. You get the root of the tree. Return the most money the thief can take without setting off the alarm.

Constraints

  • The tree has between 11 and 10410^4 nodes
  • 0≤0 \le Node.val ≤104\le 10^4

Sample 1 · Input

root = [3,2,3,null,3,null,1]

Output

7

Sample 2 · Input

root = [3,4,5,1,3,null,1]

Output

9

In the first sample, the root 3 has a left child 2 and a right child 3; the 2 has a right child 3, and the right-hand 3 has a right child 1. Robbing the root and the two grandchildren gives 3+3+1=73 + 3 + 1 = 7. In the second, the root 3 has children 4 and 5, and robbing those two gives 4+5=94 + 5 = 9, more than any set that includes the root.

A natural first attempt keeps one number per subtree: let best(v) be the most money in vv’s subtree, and build it from best of the two children. In the second sample, best(4) = 4 and best(5) = 5. If the thief robs the root, neither child may be robbed, so the root needs the best of each child’s subtree without that child. But the number 5 does not say whether house 5 was robbed, and the best without house 5 is only 1. The root could find that 1 by reaching past its children to the subtrees of its grandchildren. That works, but it makes every node look two levels down. A simpler fix is to have every subtree report two numbers instead of one.