LeetCode 198 · Medium · 1-D Dynamic Programming

House Robber

Each house on a street holds nums[i] in cash. Robbing two neighbouring houses sets off the alarm. Return the most cash you can take.

O(n)time
O(1)space
rob / skipone choice per house

comma-separated cash amounts · 1–12 houses · 0 to 400 each

vs

best dp table · best[i] = most cash from houses 0..i · the code keeps only rob1 and rob2

public int rob(int[] nums) { int rob1 = 0; // best up to 2 back int rob2 = 0; // best up to 1 back for (int n : nums) { int temp = Math.max(n + rob1, rob2); // rob vs skip rob1 = rob2; rob2 = temp; } return rob2;}
n
—
rob1
—
rob2
—
temp
—
choice
—

Why it works

  1. Brute force tries every set of houses with no two neighbours: about 1.6ⁿ of them, exponential. Greedy fails too: taking every other house misses [2,1,1,2], where the best (2 + 2) skips two houses in a row.
  2. One choice per house: best[i] = max(nums[i] + best[i−2], best[i−1]). Rob house i and you cannot have robbed i−1, so add to the best up to i−2. Skip it and keep the best up to i−1.
  3. Invariant: after each house, rob2 is the best from all houses so far and rob1 the best without the last one. Only those two are read, so O(n) time and O(1) space.
  4. Pitfall: compute temp from the old rob1 and rob2 before overwriting either. And rob2 does not mean "robbed the previous house": it may have skipped it, which is why the max never breaks the no-neighbours rule.
  5. Which houses? Two variables forget the choices. Keep the full table and walk back from the end: if best[i] ≠ best[i−1], house i was robbed, jump to i−2; otherwise step to i−1.
  6. Follow-ups: House Robber II puts the houses in a circle, so run this twice, on Arrays.copyOfRange(nums, 1, n) and Arrays.copyOfRange(nums, 0, n - 1). House Robber III on a tree returns a rob/skip pair per node. Delete and Earn reduces to this problem.