House Robber

You are given an integer array nums where nums[i] is the amount of money in house i. You cannot rob two adjacent houses. Return the maximum amount you can rob.

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 100

Examples

How to think about it

At every house i you face exactly one binary decision: rob it or skip it.

• If you skip house i → best loot = same as best through house i-1.
• If you rob house i → best loot = nums[i] + best through house i-2 (must skip i-1).

There are four approaches: brute-force recursion (O(2ⁿ)), memoization (O(n) time + space), bottom-up DP (O(n) time + space), and the space-optimized rolling window (O(n) time, O(1) space). The last two are worth visualizing — the first two are shown below as code only.

1. Recursion — O(2ⁿ) time

def rob(self, nums):
    def dfs(i):
        if i >= len(nums): return 0
        return max(dfs(i + 1),           # skip
                   nums[i] + dfs(i + 2)) # rob
    return dfs(0)

2. Memoization — O(n) time, O(n) space

def rob(self, nums):
    memo = {}
    def dfs(i):
        if i >= len(nums): return 0
        if i in memo: return memo[i]
        memo[i] = max(dfs(i + 1), nums[i] + dfs(i + 2))
        return memo[i]
    return dfs(0)

3. Bottom-Up DP — O(n) time, O(n) space

Build a dp array left to right. dp[i] = max loot achievable using houses 0 through i. Two base cases handle the first two houses, then the recurrence fills the rest.

4. Space-Optimized — O(n) time, O(1) space

Since the recurrence only ever reads the two previous dp values, you don't need the whole array. Two rolling variables — rob1 (best at i-2) and rob2 (best at i-1) — slide forward with each house. After the loop, rob2 is the answer.

Where people go wrong

Wrong recurrence — adding to the skip branch

The most common mistake is max(dp[i-1] + nums[i], dp[i-2]). Skipping house i earns nothing new — you keep exactly what you had.

# WRONG — adds nums[i] to the skip branch
dp[i] = max(dp[i-1] + nums[i], dp[i-2])

# CORRECT — adds nums[i] only when robbing
dp[i] = max(dp[i-1], nums[i] + dp[i-2])

Initialising dp[1] as just nums[1]

dp[1] should be max(nums[0], nums[1]) — the richer of the first two houses. Setting it to nums[1] alone loses the case where house 0 is more valuable.

Not handling length-1 input in bottom-up

With one house, accessing dp[1] is an out-of-bounds read. Guard with if len(nums) == 1: return nums[0] before setting dp[1]. The space-optimized solution avoids this — the loop runs once and sets rob2 = nums[0] naturally.

Quick mental tests

• [1] → 1 (single house)
• [1, 2] → 2 (take the bigger one)
• [2, 1, 1, 2] → 4 (rob houses 0 and 3)
• [100, 1, 1, 100] → 200 (rob houses 0 and 3)
• [0, 0, 0] → 0

What to do next

• House Robber IIMediumSame DP but houses form a circle — run the linear solution twice on two subarrays.›
• Min Cost Climbing StairsEasySame two-variable sliding window, but minimising cost instead of maximising loot.›
• Climbing StairsEasyFibonacci recurrence with two rolling variables — the structural twin of House Robber.›
• Delete and EarnMediumReduce to House Robber after bucketing values — taking v bans v-1 and v+1.›