House Robber

Signal

"Maximize a value along a line, but taking element i forbids its immediate neighbor" is an adjacent-exclusion choice — at every position you decide skip-or-take, and "take" reaches back past the excluded neighbor to the best result before it.

Approach

At house i, you either skip it (best-so-far stays at the value through i-1) or rob it (its cash plus the best-so-far through i-2, since i-1 is now off-limits). Track the best value through the previous two houses as you sweep left to right.

Skeleton

skip, take = 0, 0   # best through i-2, best through i-1
for money in houses:
    skip, take = take, max(take, skip + money)
return take

Solution

def rob(nums: list[int]) -> int:
    skip, take = 0, 0
    for money in nums:
        skip, take = take, max(take, skip + money)
    return take

Complexity

O(n) time — one pass. O(1) space — two rolling variables instead of a dp array, since each position only needs the best totals through the previous two houses.

Pitfalls

• Comparing nums[i] to nums[i-1] directly (a greedy "take the bigger one") ignores that skipping a small house can set up a much bigger one two houses later — this problem needs the DP, not a greedy rule.
• Forgetting that "skip" doesn't mean "the value at i-1 alone" — it means the best total achievable through i-1, which itself may have skipped i-1.
• The circular variant (House Robber II, houses in a circle) is a common follow-up: run this same DP twice, once excluding the first house and once excluding the last, and take the max.