You are a robber. Given an array of house values, find the maximum money you can rob without robbing two adjacent houses.

How to think about it

This is the interviewer’s gentlest test of whether you can name a recurrence. The trap is to chase every combination of non-adjacent houses, which is exponential. What they want is the realisation that at each house your decision depends only on the two houses behind you — a clean two-state look-back — and that once you see that, the whole array of bookkeeping collapses into two variables.

Frame it as one choice per house. Standing at house i, you either rob it — taking its value plus the best total from two houses back, since the immediate neighbour is now off-limits — or you skip it and carry forward the best total you already had. The larger of those two wins: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Because that formula reaches back exactly two steps and no further, you never need the full dp array; keep prev2 (best two back) and prev1 (best one back), and roll them forward.

A worked example

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

print(rob([1, 2, 3, 1]))        # rob houses 0 and 2 -> 1+3
print(rob([2, 7, 9, 3, 1]))     # rob houses 0,2,4 -> 2+9+1
print(rob([5]))                 # single house
print(rob([2, 1]))              # take the bigger of the two
print(rob([100, 1, 1, 100]))    # both ends, skip the middle

# Trace the two rolling variables
def rob_verbose(nums):
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    print(f"  start: prev2={prev2}, prev1={prev1}")
    for i in range(2, len(nums)):
        new = max(prev1, prev2 + nums[i])
        print(f"  i={i}, nums[i]={nums[i]}: max(skip={prev1}, rob={prev2}+{nums[i]}={prev2+nums[i]}) -> {new}")
        prev2, prev1 = prev1, new
    return prev1

print("Trace for [2,7,9,3,1]:")
rob_verbose([2, 7, 9, 3, 1])

4
12
5
2
200
Trace for [2,7,9,3,1]:
  start: prev2=2, prev1=7
  i=2, nums[i]=9: max(skip=7, rob=2+9=11) -> 11
  i=3, nums[i]=3: max(skip=11, rob=7+3=10) -> 11
  i=4, nums[i]=1: max(skip=11, rob=11+1=12) -> 12

Read the trace as a running tug-of-war between “skip” and “rob.” At i=2 robbing wins (2+9=11 beats 7), so the best jumps to 11. At i=3 skipping wins — 7+3=10 is not worth losing the 11 you already banked — so the total holds. At i=4 robbing edges ahead again to 12, which is the answer: houses 0, 2, and 4 for 2+9+1. The [100, 1, 1, 100] case returning 200 is the reassuring sanity check that the two ends can both be taken.