Dynamic Programming21 sections · 916 units
Open in Course

Vocabulary - Subtree

The building block

A subtree rooted at node vv includes vv and all nodes below it. When you compute dp[v]dp[v], you only need information from vv's subtree. This is why tree DP works: each subtree is independent.

Once you know the answer for every child's subtree, you can compute the answer for the parent. Leaves have trivial subtrees (just themselves), so they're your base cases. If you try to compute dp[v]dp[v] before computing dp[child]dp[\text{child}], you'll be missing the values you need. The order matters.