House Robber
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.
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
Intuition
House robber maximises the loot from a row of houses, with one rule: adjacent houses cannot both be robbed, or the alarm triggers.
A greedy instinct — take the largest values, or take every alternate house — fails immediately. On [2, 1, 1, 2], alternating gives 3 while robbing the first and last gives 4. The choice at each house depends on choices made earlier, which is the signature of dynamic programming.
At each house there are exactly two options:
- Rob it and add its value to the best total from two houses back, or skip it and keep the best total from the previous house.
So dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The i-2 term is where the adjacency rule lives — robbing house i forces skipping i-1, so the total must come from before it.
Base cases anchor the recurrence: dp[0] = nums[0], and dp[1] = max(nums[0], nums[1]), since with two houses only the larger may be taken.
Only the previous two values are ever read, so the array collapses to two rolling variables and O(1) space. The update order matters when rolling: compute the new value, then shift, or the old dp[i-2] is lost before it is used.
The answer is the final value, which already accounts for every valid combination — no scan of the table is needed.
House Robber II arranges the houses in a circle, making the first and last adjacent, and is solved by running this same routine twice over two ranges.
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
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n) time and O(1) space.
Reject the greedy approaches
Taking alternate houses fails on [2, 1, 1, 2] — alternating gives 3, but robbing the ends gives 4. Each choice depends on earlier ones, which forces a DP.
State the two options
At each house: rob it and add to the best total from two houses back, or skip it and keep the previous best. These are the only possibilities.
Write the recurrence
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The i-2 term encodes the adjacency rule — robbing house i forces skipping the one before it.
Set the base cases
dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]). With two houses only the larger may be taken, which anchors everything after.
Collapse to two variables
Only the previous two values are read, so the array reduces to two rolling variables — O(1) space with no change in logic.
Mind the update order
Compute the new value before shifting the variables. Overwriting first loses the dp[i-2] value the calculation still needs.
Cost of the scan
One pass with constant work per house gives O(n) time and O(1) space. House Robber II circles the row and runs this routine twice.
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.