House Robber: The Pick-or-Skip DP Template

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.

Intuition

At each house i you face a binary decision: rob it (and forfeit the right to rob i - 1) or skip it (and inherit the best plan from i - 1). The two cases cover every possibility, so the best plan up to i is max(dp[i - 1], dp[i - 2] + nums[i]). Because dp[i] only depends on the two prior values, the entire array collapses into two rolling scalars.

Explanation with 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.

i      0   1   2   3   4
nums   2   7   9   3   1
dp     2   7  11  11  12

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

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

Code

Here prev1 is the answer up to and including the current house considered, and prev2 is the answer two positions back.

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

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int value : nums) {
            int cur = Math.max(prev1, prev2 + value);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        for (int value : nums) {
            int cur = max(prev1, prev2 + value);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

Edge Cases

• Empty array: return 0. The two-variable version handles this naturally.
• 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.

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: houses arranged in a circle; solve twice and take the max.
• House Robber III: houses arranged in a binary tree; same recurrence on tree nodes.
• Delete and Earn: reduces to House Robber after bucketing values.
• Paint House: pick-or-skip generalized to three colors.
• Maximum Sum of Non-Adjacent Elements: identical recurrence under a different name.

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.