198. House Robber

House Robber is the DP problem that teaches the take-or-skip decision — one of the most common shapes in one-dimensional dynamic programming. Once you can write its recurrence in one line, House Robber II, Delete and Earn, and a handful of others fall to the same idea.

The problem

You’re given an array where each entry is the money in a house along a street, and you want to rob the most you can — but you can’t hit two adjacent houses (their alarms are linked). Return the maximum total. (Full statement on LeetCode.)

For [2, 7, 9, 3, 1] the best is 2 + 9 + 1 = 12, not the tempting 7 + 3.

Intuition: at each house, take it or skip it

Walk the street one house at a time and ask a single question at house i: do I rob it or not?

• Skip it, and the best I can have is whatever was best through house i-1.
• Rob it, and I add its money to the best through house i-2 — because i-1 is now off-limits.

So the most money through house i is:

$\text{best}(i) = \max\big(\text{best}(i-1),\; \text{best}(i-2) + \text{nums}[i]\big)$

That max is the whole problem. The “skip” branch carries the running best forward; the “rob” branch is what enforces the no-adjacent rule by reaching two houses back instead of one.

Solution

Each answer needs only the previous two, so two rolling variables replace the array:

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;   // best through i-2, best through i-1
        for (int money : nums) {
            int cur = Math.max(prev1, prev2 + money);  // skip vs. rob
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Starting both at 0 handles the empty and single-house cases for free — the first house just becomes max(0, 0 + nums[0]).

Complexity

	Time	Space
Rolling DP	$O(n)$	$O(1)$

One pass, two variables. A full dp[] array works too but wastes $O(n)$ space you never need.

In an interview

Lead with the recurrence in words — “at each house I take the better of skipping it or robbing it plus the best from two houses back” — then write the two-variable loop. The trap interviewers watch for is reaching back only one house on the “rob” branch, which quietly allows adjacent robberies. Naming why it’s i-2 shows you understand the constraint, not just the code.

The circular-street version is House Robber II, which reuses this exact function twice; the take-or-skip shape recurs across the 1D DP pattern.

References

• LeetCode 198 — House Robber