Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 337 House Robber III - Key Observation

Rob or skip each node

If you rob node vv, you get vv's money but cannot rob vv's children. You can still rob grandchildren. If you skip node vv, you get no money from vv, but you're free to rob or skip each child independently.

This creates a dependency: your choice at vv constrains your choices at vv's children. You need to track both possibilities. For each node, store 22 values: the best result when you rob it and the best when you skip it.