TL;DR
At each house choose “rob” (skip the neighbor) or “skip,” taking the max — collapsed to two rolling scalars: O(n) time, O(1) space.
The recurrence
Let best(i) be the most money obtainable from houses 0 … i. The decision at house i is binary — rob it (then house i-1 is off-limits) or skip it:
best(i) = max( best(i-1), best(i-2) + nums[i] )
best(0) = nums[0]
best(1) = max(nums[0], nums[1])
answer = best(n-1)
Approach 1 — Brute-force recursion
Recurse on “rob house i and jump to i-2” vs. “skip house i.”
class Solution:
def rob(self, nums: list[int]) -> int:
def best(i: int) -> int:
if i < 0:
return 0
return max(best(i - 1), best(i - 2) + nums[i])
return best(len(nums) - 1)
Complexity: O(2^n) time, O(n) stack.
Why the constraints kill it: each call branches in two, so the same best(i) is recomputed exponentially often — infeasible even for n = 100.
Approach 2 — Top-down memoization
The insight: only n distinct subproblems best(0) … best(n-1); cache each.
from functools import cache
class Solution:
def rob(self, nums: list[int]) -> int:
@cache
def best(i: int) -> int:
if i < 0:
return 0
return max(best(i - 1), best(i - 2) + nums[i])
return best(len(nums) - 1)
Complexity: O(n) time, O(n) space (cache + stack).
Approach 3 — Bottom-up tabulation
The insight: compute best(0) upward; each value needs only the two before it.
class Solution:
def rob(self, nums: list[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[n - 1]
Walkthrough (nums = [2, 7, 9, 3, 1]):
dp[0] = 2dp[1] = max(2, 7) = 7dp[2] = max(dp[1], dp[0] + 9) = max(7, 11) = 11dp[3] = max(dp[2], dp[1] + 3) = max(11, 10) = 11dp[4] = max(dp[3], dp[2] + 1) = max(11, 12) = 12
Return dp[4] = 12. ✓
Complexity: O(n) time, O(n) space.
Approach 4 — Space-optimized (two rolling scalars)
The insight: dp[i] reads only dp[i-1] and dp[i-2], so two variables suffice — no array.
class Solution:
def rob(self, nums: list[int]) -> int:
rob_prev2, rob_prev1 = 0, 0 # best two/one houses ago
for money in nums:
rob_prev2, rob_prev1 = rob_prev1, max(rob_prev1, rob_prev2 + money)
return rob_prev1
Walkthrough (nums = [1, 2, 3, 1]), tracking (rob_prev2, rob_prev1):
| house | money | max(rob_prev1, rob_prev2 + money) | new (prev2, prev1) |
|---|
| — | — | — | (0, 0) |
| 0 | 1 | max(0, 0+1) = 1 | (0, 1) |
| 1 | 2 | max(1, 0+2) = 2 | (1, 2) |
| 2 | 3 | max(2, 1+3) = 4 | (2, 4) |
| 3 | 1 | max(4, 2+1) = 4 | (4, 4) |
Return rob_prev1 = 4. ✓ Seeding both scalars to 0 folds the base cases in cleanly (no special-casing n = 1).
Complexity: O(n) time, O(1) space.
Common pitfalls
- Greedy “rob every other house.” Taking all even indices (or all odd) is wrong:
[2, 1, 1, 2] should give 4 (houses 0 and 3), which no fixed parity captures. The max in the recurrence is essential.
- Base case for
n = 1. The tabulated version must guard dp[1] when there is only one house; the rolling-scalar version sidesteps this by starting both at 0.
- Assuming positive values force a rob. Values can be 0; the recurrence still handles them, but don’t hand-optimize on the assumption every house is worth taking.
- Confusing “adjacent in the array” with “adjacent in value.” The constraint is on positions, not amounts — only index-neighbors trip the alarm.
Pattern takeaway
House Robber is the canonical “take-it-or-leave-it with a gap” DP: for each element decide include-and-skip-the-neighbor vs. exclude, and carry the best of both forward. The same two-variable recurrence powers a whole family — maximum-sum non-adjacent subsequence, and its variants (circular street, binary-tree houses) that reuse this core by running it on two slices or two return values. When each state depends only on a constant window behind it, finish with rolling scalars for O(1) space.