Graph Theory37 sections · 1633 units
Open in Course

Include/Exclude Transitions

Combining child states

If you include node vv, you cannot include its children (constraint in many problems). So: dp[v][1] = value of vv + sum of dp[child][0] for all children. If you exclude node vv, each child can be included or excluded independently: dp[v][0] = sum of max(dp[child][0], dp[child][1]) for all children.

This include/exclude pattern appears in House Robber III, maximum independent set, and similar problems. The insight is that including vv forces excluding adjacent nodes.