Medium
Dynamic Programming
House Robber
At each house choose the better of robbing it (plus two back) or skipping it.
Approach
Define best(i) = max(best(i−1), best(i−2) + nums[i]) — skip this house, or take it and whatever was optimal two houses back. Roll two variables forward for O(1) space. The recurrence enforces the no-adjacent constraint automatically.
Time complexity
O(n)
Space complexity
O(1)
Common mistake
Greedily taking all even or all odd houses — the optimal choice depends on values, not parity.
See it run, step by step
Generate an interactive lesson for House Robber — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on House Robber