Graph Theory37 sections · 1633 units
Open in Course

LeetCode 337 House Robber III - State Definition

Two values per node

Define dp[v][0] = maximum value you can rob from subtree rooted at vv if you do NOT rob house vv. Define dp[v][1] = maximum value you can rob from subtree rooted at vv if you DO rob house vv.

These two states capture all possibilities. For each node, you either rob it or skip it. The transition depends on which choice you made. This two-state pattern solves the constraint that adjacent houses cannot both be robbed.