House Robber

Problem Statement

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

Input:  nums = [1, 2, 3, 1]
Output: 4
Why:    take house 0 (1) and house 2 (3)

Input:  nums = [2, 7, 9, 3, 1]
Output: 12
Why:    take 2 + 9 + 1, not 7 + 3

Intuition

The tempting rule is "always take the biggest available house". Watch it fail:

nums = [2, 7, 9, 3, 1]
        0  1  2  3  4

Greedy: take 9 (the largest), which blocks 7 and 3.
        Then take 2 and 1  →  total 12.
Best:   2 + 9 + 1                →  12.   Greedy is right, by luck.

nums = [6, 10, 6, 1, 1]
        0   1  2  3  4

Greedy: take 10 (the largest), which blocks BOTH sixes.
        Only index 3 or 4 is left  →  total 11.
Best:   6 + 6 + 1  (indices 0, 2, 4)  →  13.

Since you cannot decide greedily, you must consider both options — and that is the shape of dynamic programming.

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

That single line is the entire algorithm. Everything else is bookkeeping.

Why this is DP and not just recursion

Write that formula as plain recursion and best(3) gets computed by best(5), and again by best(4), and so on — the same subproblems recomputed exponentially many times.

Both DP conditions hold:

So compute each best(i) once, in order, and reuse it.

The real-world version

You are choosing which shifts to work. Two shifts back to back are not allowed. Standing at Friday, you ask: is it better to work Friday plus my best through Wednesday, or to skip Friday and keep my best through Thursday?

You do not need to remember which specific days you picked — only the two running totals.

Approach

Watch it run

Solution

def rob(nums: list[int]) -> int:
    """Maximum sum of non-adjacent values, in O(1) space."""
    prev2 = 0  # best through house i-2
    prev = 0   # best through house i-1

    for num in nums:
        # Take this house (skipping the neighbour) or skip it.
        current = max(num + prev2, prev)

        # Shift the window. prev2 must be updated BEFORE prev is overwritten.
        prev2 = prev
        prev = current

    return prev


def rob_table(nums: list[int]) -> int:
    """The same recurrence with an explicit table — clearer, uses O(n) space."""
    if not nums:
        return 0

    n = len(nums)
    best = [0] * (n + 1)
    best[1] = nums[0]

    for i in range(2, n + 1):
        # best[i] means "best using the first i houses".
        best[i] = max(nums[i - 1] + best[i - 2], best[i - 1])

    return best[n]

prev = current      ← WRONG if done first
prev2 = prev        ← now prev2 gets the NEW value, not the old one

Complexity Analysis

• Time — one pass, constant work per house.
• Space — two variables, regardless of input size. The table version is O(n) and is worth writing first if the recurrence is not yet obvious; collapsing to two variables is a mechanical last step.

Edge Cases

Related Problems

• Climbing Stairs — the same two-variable shape, adding instead of maximising
• Coin Change — when the window is not fixed at two
• Best Time to Buy and Sell Stock — a DP table collapsed to a single running value
• Dynamic Programming — the four stages in detail