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.
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
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.