DPDynamic Programming
Tree DP (maximum-weight independent set)
State is a node (plus a small flag); each node combines the answers of its children in post-order.
take / skip per node
| node | weight | take | skip |
|---|---|---|---|
| n3 | 4 | — | — |
| n4 | 8 | — | — |
| n1 | 5 | — | — |
| n5 | 3 | — | — |
| n6 | 7 | — | — |
| n2 | 12 | — | — |
| n0 | 10 | — | — |
postorder (the order the recurrence is legal in)
1. n3 (leaf)2. n4 (leaf)3. n1 ← n3, n44. n5 (leaf)5. n6 (leaf)6. n2 ← n5, n67. n0 ← n1, n2
1/26An independent set may not contain two adjacent nodes, so every node needs two answers rather than one: the best total for its subtree when the node is taken, and the best when it is not. A single number per node cannot work, because whether n0's children are usable is decided one level up.
Node being resolvedChild value being readResolved (take, skip) knownIn the chosen independent set
PseudocodeLearn Tree DP →
1solve(u): # postorder — children resolve first2 for each child c of u: solve(c)3 take[u] = value[u] + Σ_c skip[c] # u is in the set → no child may be4 skip[u] = Σ_c max(take[c], skip[c]) # u is out → each child picks its own best5answer = max(take[root], skip[root])6reconstruct: walk down, taking u only when take[u] wins and u is still allowedVariables
nodes7
weights10, 5, 12, 4, 8, 3, 7
Complexity
worst O(n · k) for k statuses per node (O(n) typically); O(n · K²) for subtree-knapsack merges with the small-to-large bound
space O(n) table + O(height) recursion
Speed