House Robber

Problem

Houses along a street each hold some amount of money, given as an array nums. You want to rob as much as possible in one night, but robbing two adjacent houses trips a shared alarm. Choose a subset of houses with no two neighbors to maximize the total money taken.

Return that maximum total.

Examples

• nums = [1, 2, 3, 1] → 4 — rob houses 0 and 2 (1 + 3); robbing 1 and 3 gives only 3.
• nums = [2, 7, 9, 3, 1] → 12 — rob houses 0, 2, 4 (2 + 9 + 1).
• nums = [5] → 5 — the only house, so take it.

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

The input is small, so an O(n) solution is more than fast enough. The point is the no-two-adjacent decision structure, a template that recurs across many DP problems.

Think about it first

TL;DR

At each house choose “rob” (skip the neighbor) or “skip,” taking the max — collapsed to two rolling scalars: O(n) time, O(1) space.

The recurrence

Let best(i) be the most money obtainable from houses 0 … i. The decision at house i is binary — rob it (then house i-1 is off-limits) or skip it:

best(i) = max( best(i-1),  best(i-2) + nums[i] )
best(0) = nums[0]
best(1) = max(nums[0], nums[1])
answer  = best(n-1)

Approach 1 — Brute-force recursion

Recurse on “rob house i and jump to i-2” vs. “skip house i.”

def rob(nums: list[int]) -> int:
    def best(i: int) -> int:
        if i < 0:
            return 0
        return max(best(i - 1), best(i - 2) + nums[i])
    return best(len(nums) - 1)

Complexity: O(2^n) time, O(n) stack.

Each call branches in two, and the branches overlap: the same best(i) is recomputed exponentially often, which is infeasible even for n = 100. The tree below shows the recomputation for n = 5 — best(2) is evaluated twice and best(1) three times, and the duplication compounds as n grows.

flowchart TD
    b4["best(4)"] --> b3["best(3)"]
    b4 --> b2a["best(2)"]
    b3 --> b2b["best(2)"]
    b3 --> b1a["best(1)"]
    b2a --> b1b["best(1)"]
    b2a --> b0a["best(0)"]
    b2b --> b1c["best(1)"]
    b2b --> b0b["best(0)"]

Approach 2 — Top-down memoization

There are only n distinct subproblems, best(0) … best(n-1), so cache each one.

from functools import cache

def rob(nums: list[int]) -> int:
    @cache
    def best(i: int) -> int:
        if i < 0:
            return 0
        return max(best(i - 1), best(i - 2) + nums[i])
    return best(len(nums) - 1)

Complexity: O(n) time, O(n) space (cache + stack).

Approach 3 — Bottom-up tabulation

Compute the values from best(0) upward; each one needs only the two before it.

def rob(nums: list[int]) -> int:
    n = len(nums)
    if n == 1:
        return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[n - 1]

Walkthrough (nums = [2, 7, 9, 3, 1]):

• dp[0] = 2
• dp[1] = max(2, 7) = 7
• dp[2] = max(dp[1], dp[0] + 9) = max(7, 11) = 11
• dp[3] = max(dp[2], dp[1] + 3) = max(11, 10) = 11
• dp[4] = max(dp[3], dp[2] + 1) = max(11, 12) = 12

Return dp[4] = 12.

Complexity: O(n) time, O(n) space.

Approach 4 — Space-optimized (two rolling scalars)

dp[i] reads only dp[i-1] and dp[i-2], so two variables suffice and the array can be dropped.

def rob(nums: list[int]) -> int:
    rob_prev2, rob_prev1 = 0, 0               # best two/one houses ago
    for money in nums:
        rob_prev2, rob_prev1 = rob_prev1, max(rob_prev1, rob_prev2 + money)
    return rob_prev1

Walkthrough (nums = [1, 2, 3, 1]), tracking (rob_prev2, rob_prev1):

Return rob_prev1 = 4. Seeding both scalars to 0 folds in the base cases, so there is no need to special-case n = 1.

Complexity: O(n) time, O(1) space.

Common pitfalls

• Greedy “rob every other house.” Taking all even indices (or all odd) is wrong: [2, 1, 1, 2] should give 4 (houses 0 and 3), which no fixed parity captures. The max in the recurrence is essential.
• Base case for n = 1. The tabulated version must guard dp[1] when there is only one house; the rolling-scalar version sidesteps this by starting both at 0.
• Assuming positive values force a rob. Values can be 0; the recurrence still handles them, but don’t hand-optimize on the assumption every house is worth taking.
• Confusing “adjacent in the array” with “adjacent in value.” The constraint is on positions, not amounts — only index-neighbors trip the alarm.

Pattern takeaway

House Robber is the canonical “take-it-or-leave-it with a gap” DP: for each element decide include-and-skip-the-neighbor vs. exclude, and carry the best of both forward. The same two-variable recurrence powers a whole family — maximum-sum non-adjacent subsequence, and its variants (circular street, binary-tree houses) that reuse this core by running it on two slices or two return values. When each state depends only on a constant window behind it, finish with rolling scalars for O(1) space.