← DSADSA 5.8
DP on Trees
Not started yet — 4 problems queued; the DP specialization of the tree-recursion habits from Trees.
A post-order DFS where each node combines results from its children — often returning multiple states, such as "best if I include this node" vs. "best if I don't".
Sub-patterns
- A — Include/Exclude at a Node. Two states per node: with it, without it.
- B — Subtree Aggregation. Combine children's results into a single value at each node.
- C — Diameter-Style DP. Track a running best that spans across a node's children.
Practice set (4)
- Medium — House Robber III (also relevant to DP Foundations), Distribute Coins in Binary Tree
- Hard — Binary Tree Cameras, Longest Path With Different Adjacent Characters
Pending
Include/Exclude at a Node
Track two states per node — the best result with this node included, and without it.
Pending
Subtree Aggregation
Combine children's results into a single value at each node during a post-order DFS.
Pending
Diameter-Style DP
Track a running best-so-far that can span across a node's children, not just down one branch.
Notes from readers
Comments — via GitHub