Graph Theory37 sections · 1633 units
Open in Course

Include/Exclude Pattern

Two states per node

Some problems need two DP values per node: one if you include it in the solution, one if you exclude it. Example: maximum independent set on trees. ext{dp}[v][0] = max value excluding vv. ext{dp}[v][1] = max value including vv.

Transitions depend on whether you include or exclude each node. The constraint (cannot pick adjacent nodes) determines how you combine child values. This two-state pattern appears in many improvement problems.