House Robber
Each house on a street holds some amount of money. Robbing two adjacent houses triggers the alarm. Return the maximum you can take.
Open on LeetCode ↗Intuition
Greedily grabbing the biggest houses fails: on [2,7,9,3,1] the greedy takes 9, then is blocked from 7 and 3, and settles for 9+2+1 = 12 by luck — but on [2,1,1,2] greedy picking the first 2 then getting stuck yields 4 while the correct answer is also 4, and on other inputs it loses outright. The reliable framing is a per-house binary choice: at house i either rob it, adding its value to the best total from i-2, or skip it and inherit the best total from i-1. Take the larger. Compare totals, never house values.
Two running states — the best total if you take the current house, and the best if you skip it. Taking requires having skipped the previous one; skipping keeps whichever was better. Any "no two adjacent" constraint collapses to this pair of alternating recurrences.
Approach
State the choice at a single house
Define dp[i] as the maximum loot obtainable considering only houses 0..i. Standing at house i there are exactly two options. Rob it: you gain nums[i], but house i-1 is now off-limits, so the rest of your haul is dp[i-2]. Skip it: your haul is whatever was already best up to i-1, namely dp[i-1]. Hence dp[i] = max(nums[i] + dp[i-2], dp[i-1]).
Set the base cases
dp[0] = nums[0] — with one house, rob it. dp[1] = max(nums[0], nums[1]) — adjacent, so take the better one. From index 2 onward the recurrence applies unchanged. In code it is often cleaner to fold dp[1] into the loop by treating dp[-1] as 0, which is what the implementation below does with the if j >= 2 guard.
Fill forward and then collapse the space
One left-to-right pass fills the table; the answer is dp[n-1]. Because each cell reads only dp[i-1] and dp[i-2], the array collapses to two variables — same reduction as Climbing Stairs, and the reason both problems are usually taught together. O(n) time, O(1) space.
Solution & live demo
Common pitfalls
Assuming the answer alternates evens and odds
return max(sum(nums[::2]), sum(nums[1::2]))
take, skip = skip + x, max(skip, take)
The optimal set isn't always strictly alternating — on [2, 1, 1, 2] the answer takes indices 0 and 3, skipping two in a row. Only the DP considers those gaps.
Updating the two states sequentially
take = skip + x skip = max(skip, take)
take, skip = skip + x, max(skip, take)
The second line reads the take just overwritten, so it uses this house's value when deciding to skip this house — allowing two adjacent houses to be robbed. Both updates must read the previous iteration's values.
Returning take alone
return take
return max(take, skip)
The best plan may end by skipping the final house — on [5, 1] the answer is 5, which lives in skip after the last step. Both endings have to be considered.
Edge cases
dp[0] = nums[0]; the loop never runs and that value is returned.
The recurrence with dp[-1] treated as 0 gives max(nums[1], nums[0]) — the better of the two, since both cannot be robbed.
The answer is every other house, which the DP finds automatically; no tie-breaking rule is needed.
This is exactly where greedy-by-position fails and the DP does not: it evaluates both totals rather than committing to a local decision.
Complexity
take is the best total that robs the current house; skip is the best that does not.