4.23.3 — House Robber

LeetCode 198 · Medium · ★ Blind 75

The problem

Each house holds some money. You cannot rob two adjacent houses. Return the most you can take.

[1,2,3,1]      →  4     (houses 0 and 2)
[2,7,9,3,1]    →  12    (houses 0, 2 and 4)

Why greedy fails

The obvious greedy rule is "always take the biggest remaining house you are allowed to take". Break it in one line:

[2, 7, 9, 3, 1]

Greedy takes 9 first, which blocks 7 and 3, then takes 2 and 1 for a total of 12. That happens to be right here — so try:

[2, 1, 1, 2]

Greedy takes a 2, blocks its neighbour, takes the other 2 → 4. Correct again. Now:

[8, 10, 9]

Greedy takes 10, blocking both neighbours, total 10. The right answer is 8 + 9 = 17.

That is the structural tell from 4.22: taking a house removes an option later. A choice that constrains future choices is exactly what greedy cannot see, and it means DP.

The pattern

At each house you have exactly two options, and they cover everything:

• Rob it — then you must have skipped house i − 1, so you add nums[i] to the best total up to i − 2.
• Skip it — then your total is whatever the best was up to i − 1.

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

Read aloud: the best up to house i is the better of robbing it — which forces you back two — or skipping it and keeping what you had.

"Take it or leave it, and taking it constrains what came before" is the single most common 1-D DP shape. Once you can write that line, most of this chapter is variations on it.

The solution

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob_prev, skip_prev = 0, 0           # dp[i-2], dp[i-1]

        for n in nums:
            rob_prev, skip_prev = skip_prev, max(n + rob_prev, skip_prev)

        return skip_prev

TypeScript

function rob(nums: number[]): number {
  let two = 0, one = 0;                      // dp[i-2], dp[i-1]

  for (const n of nums) {
    [two, one] = [one, Math.max(n + two, one)];
  }

  return one;
}

Two variables and one line. It is worth being able to read that line without hesitation:

• n + rob_prev — rob this house, adding to the best from two back.
• skip_prev — do not rob it, so keep the best from one back.
• The pair assignment shifts the window forward: what was "one back" becomes "two back", and the new answer becomes "one back".

Both variables start at 0, which handles the empty array and the first house with no special case. For nums = [5], one iteration gives max(5 + 0, 0) = 5. ✓

If the two-variable version is hard to trust, write the array first:

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

Then collapse it. That is the honest order to work in, and showing the collapse is worth more than producing the tight version immediately.

Trace

[2, 7, 9, 3, 1]

house	value	rob it (n + two)	skip it (one)	new one
0	2	2 + 0 = 2	0	2
1	7	7 + 0 = 7	2	7
2	9	9 + 2 = 11	7	11
3	3	3 + 7 = 10	11	11
4	1	1 + 11 = 12	11	12

Answer 12. Notice house 3 is skipped because keeping the 11 beats taking 3.

Complexity

O(n) time, O(1) space.

Where this goes next

This recurrence appears everywhere once you know it:

• House Robber II — the houses form a circle, so the first and last are adjacent. Run this twice on two ranges. 4.23.4.
• House Robber III — a tree instead of a line. Each node returns two values: the best if it is robbed, and the best if it is not. Same idea, tree shape.
• Delete and Earn — deleting value v removes all v−1 and v+1. Bucket the values by number, and it becomes House Robber on the value axis. This reduction is the reason to learn this problem properly — the connection is not visible until you know what to look for.
• Maximum Sum of Non-Adjacent Elements, Best Sightseeing Pair — same skeleton.

What the interviewer will push on

"Why not greedy?" Give the [8, 10, 9] counterexample. Doing this before they ask is the strongest opening.

"What does dp[i] mean?" The best total considering the first i houses — not "the best if you rob house i". Being precise here prevents the usual confusion.

"Why do both variables start at 0?" It makes the empty and single-house cases fall out with no branch.

"O(1) space?" Two variables, and show the collapse from the array.

"What if the houses were in a circle?" House Robber II — two runs, excluding the first house in one and the last in the other.

"What if you also had to say which houses?" Keep the table and walk it backwards, checking at each step whether dp[i] came from robbing or skipping. Reconstructing the choice always needs the full table, which is the one real cost of the space optimisation.

One thing to volunteer: name the shape. "This is take-it-or-leave-it where taking constrains the previous choice — the standard 1-D DP." Then say which other problems reduce to it.

Next: 4.23.4 House Robber II — the same recurrence run twice, and the trick of removing a constraint by splitting the problem.