House Robber: DP With a Twist

You are a robber planning to hit houses along a street. Each house has a certain amount of money stashed, but there is a catch: if you rob two adjacent houses, the alarm system goes off. Given a list of non-negative integers representing the money in each house, what is the maximum amount you can steal without triggering any alarms?

This is LeetCode 198: House Robber, and it is one of the best problems for learning the "rob or skip" decision pattern in dynamic programming. If you have already worked through Climbing Stairs, this is the natural next step. Same DP skeleton, but now you have a choice at every position.

Why this problem matters

House Robber teaches you something that Climbing Stairs does not: how to model a decision at each step. In Climbing Stairs, you simply add up the ways to arrive. Here, you have to pick between two options at every house and carry the best result forward.

That rob-or-skip DP pattern shows up everywhere:

• House Robber II (circular street)
• House Robber III (tree structure)
• Delete and Earn (same logic, different setup)
• Paint House and Paint Fence problems

Master it here, and you will recognize it instantly in those harder variants.

Thinking it through

At each house you have exactly two options:

1. Rob it. You take the money from this house, but you cannot use the money from the house right before it (because that would mean two adjacent houses). So you add this house's value to the best total you had two houses ago.
2. Skip it. You walk past and keep whatever your best total was from the previous house.

The answer at each position is whichever option gives more money:

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

That is the entire recurrence. Let's see it in action.

Starting with recursion

The most direct way to express this logic is a recursive function. For position i, return the maximum of skipping (solve i-1) or robbing (value at i plus solve i-2).

def rob(nums):
    def helper(i):
        if i < 0:
            return 0
        return max(helper(i - 1), helper(i - 2) + nums[i])

    return helper(len(nums) - 1)

This is correct but slow. Each call branches into two more calls, and you end up recomputing the same subproblems over and over. For a street with 30 houses, that is over a billion calls. Time complexity: O(2^n).

Adding memoization (top-down DP)

Cache each result so you never solve the same index twice.

def rob(nums):
    memo = {}

    def helper(i):
        if i < 0:
            return 0
        if i in memo:
            return memo[i]
        memo[i] = max(helper(i - 1), helper(i - 2) + nums[i])
        return memo[i]

    return helper(len(nums) - 1)

Each index from 0 to n-1 is computed once. Time: O(n). Space: O(n) for the memo dictionary plus O(n) for the call stack. Big improvement, but we can drop the recursion entirely.

Building the DP array (bottom-up)

Instead of recursing from the end, iterate forward and fill a table. Define dp[i] as the maximum money you can collect from houses 0 through i.

The recurrence:

• dp[0] = nums[0] (one house, rob it)
• dp[1] = max(nums[0], nums[1]) (two houses, pick the richer one)
• dp[i] = max(dp[i-1], dp[i-2] + nums[i]) for i >= 2

Let's walk through nums = [2, 7, 9, 3, 1]:

At every step, the "rob" arrow (green) means "take this house plus the best from two back." The "skip" arrow (purple) means "pass on this house and keep the previous best." You just pick whichever is larger.

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]

Time: O(n). One pass through the array.

Space: O(n). The dp array.

No recursion, no call stack overhead. Just a clean loop. But we can still do better on space.

Optimizing to O(1) space

Look at the recurrence one more time: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Each value depends on only the previous two. Sound familiar? It is the same situation as Climbing Stairs. Two variables are all you need.

def rob(nums):
    if not nums:
        return 0

    prev2 = 0       # dp[i-2]
    prev1 = 0       # dp[i-1]

    for num in nums:
        current = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = current

    return prev1

Same O(n) time, but now O(1) space. Two variables instead of a full array. This is the optimal house robber LeetCode solution.

Let's trace through [2, 7, 9, 3, 1]:

• Start: prev2 = 0, prev1 = 0
• house 0 ($2): current = max(0, 0 + 2) = 2. Shift: prev2 = 0, prev1 = 2
• house 1 ($7): current = max(2, 0 + 7) = 7. Shift: prev2 = 2, prev1 = 7
• house 2 ($9): current = max(7, 2 + 9) = 11. Shift: prev2 = 7, prev1 = 11
• house 3 ($3): current = max(11, 7 + 3) = 11. Shift: prev2 = 11, prev1 = 11
• house 4 ($1): current = max(11, 11 + 1) = 12. Shift: prev2 = 11, prev1 = 12
• Return prev1 = 12

Complexity analysis

The progression from brute force to optimal follows the same four-step pipeline as every linear DP problem:

1. Write the recursive solution to get the logic right.
2. Add memoization to eliminate redundant work.
3. Convert to bottom-up to remove recursion overhead.
4. Optimize space by keeping only what the recurrence needs.

Edge cases to watch for

• Empty array: return 0. No houses, no money.
• Single house: return nums[0]. Only one choice.
• Two houses: return max(nums[0], nums[1]). Pick the richer one.
• All equal values: e.g., [5, 5, 5, 5]. Rob every other house. The O(1) solution handles this naturally.
• Large values at the ends: e.g., [100, 1, 1, 100]. Rob houses 0 and 3 for $200. Make sure your base cases do not accidentally skip the first house.

The building blocks

This problem is built on linear DP with constant state, the same fundamental pattern as Climbing Stairs and Coin Change. You iterate through a sequence, and at each position you compute a value that depends on a fixed number of previous values.

The structure:

• State: dp[i] = maximum money from houses 0 through i
• Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (the rob-or-skip decision)
• Space optimization: since you only look back two steps, replace the array with two variables

What makes House Robber interesting is the decision in the transition. In Climbing Stairs, you always add the two previous values. Here, you pick the better of two options. That "max" in the recurrence is the twist. It turns a counting problem into an optimization problem, but the underlying DP machinery is identical.

The same building block appears in:

• House Robber II (LeetCode 213): same recurrence, but the street is circular. Run the algorithm twice (once excluding the first house, once excluding the last) and take the max.
• Delete and Earn (LeetCode 740): reduce to House Robber by grouping values. Once you see the reduction, the DP is exactly the same.
• Decode Ways (LeetCode 91): same two-variable lookback, different transition logic.

Once you internalize linear DP with constant state as a reusable building block, these problems are all variations on the same theme.

From understanding to recall

You have just read through four versions of the solution, and the rob-or-skip DP pattern probably makes sense right now. But will you be able to write this solution from scratch next week? What about in an interview when the stakes are higher and nobody is walking you through it?

Understanding and recall are different skills. Spaced repetition bridges the gap. You revisit the rob-or-skip recurrence at increasing intervals, write it from scratch each time, and after a few reps the pattern is automatic. No more staring at a blank editor trying to remember whether it is dp[i-1] or dp[i-2] that gets the current value added to it.

The linear DP with constant state pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Climbing Stairs - Your first DP problem, same building block with a simpler transition (no decision, just addition)
• Coin Change - The next level of linear DP, where the lookback distance varies based on coin denominations