LeetCode House Robber: The Pick-or-Skip DP Template

LeetCode 198, House Robber, is the canonical pick-or-skip dynamic programming problem. Once you have internalized its recurrence, you will recognize the same shape in dozens of harder questions including House Robber II, Delete and Earn, and Paint House. This walkthrough builds the solution from scratch and then turns it into a reusable template.

The Problem

You are a robber planning to rob houses along a street. Each house has a non-negative integer amount of money. The only constraint: you cannot rob two adjacent houses on the same night, because that triggers the alarm. Return the maximum amount you can rob.

Example inputs and outputs:

Input:  nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 0 and house 2 -> 1 + 3 = 4.

Input:  nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob houses 0, 2, 4 -> 2 + 9 + 1 = 12.

Input:  nums = [2, 1, 1, 2]
Output: 4
Explanation: Rob houses 0 and 3 -> 2 + 2 = 4.

The core decision at each house i is binary: rob it and skip i - 1, or skip it and inherit the best from i - 1. That gives the recurrence dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]).

Brute Force

Translate the decision directly into recursion.

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

This explores both branches at every index, giving O(2^n) time. It times out around n = 35.

Optimal Solution

The state dp[i] depends only on dp[i - 1] and dp[i - 2], so we tabulate left to right and then collapse to two variables.

def rob(nums: list[int]) -> int:
    prev2, prev1 = 0, 0
    for value in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + value)
    return prev1

Here prev1 is the answer up to and including the current house considered, and prev2 is the answer two positions back. The tuple assignment performs both updates atomically.

If you prefer the explicit DP array version, it reads like this:

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    if n >= 2:
        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[-1]

Walk Through an Example

Take nums = [2, 7, 9, 3, 1].

i=0  value=2  prev2=0  prev1=max(0, 0+2)=2
i=1  value=7  prev2=2  prev1=max(2, 0+7)=7
i=2  value=9  prev2=7  prev1=max(7, 2+9)=11
i=3  value=3  prev2=11 prev1=max(11, 7+3)=11
i=4  value=1  prev2=11 prev1=max(11, 11+1)=12

Final answer: 12, matching the expected 2 + 9 + 1.

Edge Cases

• Empty array: return 0. Guard with if not nums.
• Single house: return nums[0]. The two-variable version handles this because prev1 becomes max(0, 0 + nums[0]).
• All zeros: return 0.
• Strictly increasing or decreasing arrays: the recurrence still works; no special case.
• Very large values: Python handles arbitrary precision, so no overflow concerns. In other languages, use 64-bit accumulators if values can be large.

Complexity Analysis

• Time: O(n). Single pass through the array.
• Space: O(1) for the rolling-variable version, O(n) for the table version.

The brute force recursion is O(2^n) time and O(n) stack space. Adding memoization brings it to O(n) time and O(n) space. If you want to revisit why O(2^n) blows up so fast, see /blog/big-o-notation-explained.

How to Explain It in an Interview

Use this five-step script:

1. Identify the decision: at each house, rob or skip.
2. State the recurrence in words: best_up_to(i) = max(best_up_to(i - 1), best_up_to(i - 2) + nums[i]).
3. Justify optimal substructure: the best plan for the first i houses must end in one of the two states above; no third option exists.
4. Implement bottom-up, then point out that only two prior states are needed, motivating O(1) space.
5. Trace one example to prove correctness.

Mentioning that this is the pick-or-skip template signals you have seen it before and recognize the family. Interviewers like that pattern recognition.

Related Problems

• House Robber II (LeetCode 213): houses arranged in a circle; solve twice and take the max.
• House Robber III (LeetCode 337): houses arranged in a binary tree; same recurrence on tree nodes.
• Delete and Earn (LeetCode 740): reduces to House Robber after bucketing values.
• Paint House (LeetCode 256): pick-or-skip generalized to three colors.
• Maximum Sum of Non-Adjacent Elements: identical recurrence under a different name. See more variants in /blog/dynamic-programming-classic-problems.

Wrap up

House Robber rewards the discipline of writing the recurrence first and only then thinking about code. The pick-or-skip template, dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]), will reappear constantly in interviews and competitive programming. Memorize the two-variable form, practice it once a week, and pair it with /blog/dynamic-programming-introduction so you can derive it from scratch under pressure rather than recalling it from memory.