House Robber
Problem
nums[i] is the cash inside house
i. A thief may rob any set of houses as long as no two chosen houses are
adjacent (neighbouring break-ins trigger the alarm). Return the largest total the thief
can collect.nums=[1,2,3,1]Output4 (houses 0 and 2)nums=[2,7,9,3,1]Output12 (houses 0, 2 and 4)nums=[2,1]Output21 ≤ n ≤ 100 · 0 ≤ nums[i] ≤ 400
Try it yourself
class Solution {
public int rob(int[] nums) {
}
}
i there are only two choices: skip it (keep the best
up to i-1) or rob it (its cash + the best up to i-2).
So best(i) = max(best(i-1), best(i-2) + nums[i]) — and only the last two
values are ever needed.Instinct The best answer at position i depends only on a few earlier positions (i-1, i-2, ...) - write dp[i] from its predecessors, then roll it into variables.
Memory hack Look back, pick best, roll forward - every step only remembers the last couple of stairs it stood on.
Open the 1-D Dynamic Programming guide →Approaches
Brute ForcePlain Recursion (Rob or Skip)
O(2n)Space O(n)rob(i) = best total from houses i..n-1. Either skip house
i (rob(i+1)) or take it and jump past its neighbour
(nums[i] + rob(i+2)). The same subproblems are recomputed over and over,
like naive Fibonacci.
public int rob(int[] nums) { return best(nums, 0); } private int best(int[] nums, int i) { if (i >= nums.length) return 0; int skip = best(nums, i + 1); int take = nums[i] + best(nums, i + 2); return Math.max(skip, take); }
Directly mirrors the choice, but the call tree grows exponentially.
BetterBottom-Up DP Table
O(n)Space O(n)Let dp[i] be the best loot from the first i houses.
dp[0] = 0, dp[1] = nums[0], and
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]). Each subproblem is solved
once, in order.
public int rob(int[] nums) { int n = nums.length; int[] dp = new int[n + 1]; // dp[i] = best using the first i houses dp[1] = nums[0]; for (int i = 2; i <= n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]); } return dp[n]; }
Linear time, but keeps a whole array when only two cells are ever read.
OptimalTwo Rolling Variables
O(n)Space O(1)The recurrence looks back only two steps, so replace the table with
prev (best up to i-2) and curr (best up to
i-1). For each house compute the new best and slide the window
forward.
public int rob(int[] nums) { int prev = 0; // best total up to house i-2 int curr = 0; // best total up to house i-1 for (int cash : nums) { int next = Math.max(curr, prev + cash); // skip vs. rob this house prev = curr; curr = next; } return curr; }
Dry runnums=[1,2,3,1]
- i=02i7931max(0, 0+2) → curr=2
- i=127i931max(2, 0+7) → curr=7
- i=2279i31max(7, 2+9) → curr=11
- i=32793i1max(11, 7+3) → skip
- i=427931imax(11, 11+1)=12 ✔
Same linear time with constant memory — the expected interview answer.
n = 1 or n = 2.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion (Rob or Skip) | O(2n) | O(n) |
| Better | Bottom-Up DP Table | O(n) | O(n) |
| Optimal | Two Rolling Variables | O(n) | O(1) |
- Taking all even or all odd indices — the best set can skip two houses in a row.
- Off-by-one in the table version:
dp[i]refers tonums[i-1]. - Updating
prevbefore computing the new value — overwrites data you still need.
- State the rob/skip choice first; the recurrence then writes itself.
- Go recursion → memo/table → two variables, naming each complexity.
- Mention the circular variant (House Robber II): run the linear solution twice.