AlgoMaster Logo

House Robber

Last Updated: March 28, 2026

medium
5 min read

Understanding the Problem

We have a row of houses, each with some amount of money. We want to maximize the total money we collect, but we cannot rob two houses that are next to each other. So if we rob house i, we must skip house i+1 (and house i-1).

This is not as simple as "take every other house." Consider [2, 1, 1, 100]. If you greedily take house 0 and house 2 (skipping odd indices), you get 2 + 1 = 3. But the optimal is house 0 and house 3, giving 2 + 100 = 102. The decision of whether to rob a house depends on decisions made for earlier houses.

The key observation: at each house, you have exactly two choices. Rob it (and add its value to the best you could do up to two houses back) or skip it (and carry forward the best you could do up to the previous house). This "take or skip with a neighbor constraint" structure is a textbook dynamic programming setup.

Key Constraints:

  • 1 <= nums.length <= 100 --> With n at most 100, even O(n^3) would be fast enough. But n being small does not mean we should brute-force all subsets (2^100 is astronomical). We need something smarter than exponential, but even O(n^2) is overkill here. A simple O(n) DP is perfect.
  • 0 <= nums[i] <= 400 --> Values are non-negative. This means skipping a house never helps unless it lets us rob a more valuable neighbor. We never need to worry about negative values making the "skip" choice better by default.

Approach 1: Recursion (Brute Force)

Intuition

The most natural way to think about this problem is with a recursive decision at each house. Standing at house i, we ask: should we rob it or skip it?

If we rob house i, we earn nums[i] and then solve the subproblem for houses 0 through i-2 (we must skip house i-1). If we skip house i, we solve the subproblem for houses 0 through i-1. We take whichever choice gives more money.

This recursive thinking directly models the problem, but it's slow. The same subproblem gets solved over and over. For example, computing the answer for house 5 requires answers for houses 3 and 4, and house 4 also requires house 3. This overlapping subproblem structure means the recursion tree grows exponentially.

Algorithm

  1. Define a recursive function rob(i) that returns the maximum money from houses 0 through i.
  2. Base cases: if i < 0, return 0. If i == 0, return nums[0].
  3. Recursive case: return max(rob(i - 1), nums[i] + rob(i - 2)).
  4. Call rob(n - 1) where n is the length of nums.

Example Walkthrough

1rob(4): consider house 4 (val=1). Choose max of rob(3) vs 1+rob(2)
0
2
1
7
2
9
3
3
4
1
rob(4)
1/6

Code

The recursion recomputes the same subproblems many times. What if we stored the result of each rob(i) the first time we compute it?

Approach 2: Memoization (Top-Down DP)

Intuition

The brute force recursion has the right structure, it just does too much redundant work. We can fix that by caching results. The first time we compute rob(i), we store the answer. Every subsequent call to rob(i) returns the cached value immediately.

This technique is called memoization, and it transforms our exponential solution into a linear one. Each subproblem rob(0) through rob(n-1) is solved exactly once, and each takes O(1) work (just a comparison and an addition). So the total work drops from O(2^n) to O(n).

Algorithm

  1. Create a memo array of size n, initialized to -1 (meaning "not computed yet").
  2. Define rob(i) the same as before, but before computing, check if memo[i] is already set. If so, return it.
  3. After computing, store the result in memo[i] before returning.
  4. Call rob(n - 1).

Example Walkthrough

1Initialize memo = [-1, -1, -1, -1, -1]. Start rob(4).
0
-1
1
-1
2
-1
3
-1
4
-1
1/6

Code

We're using O(n) space for the memo array plus O(n) for the recursion stack. Since rob(i) only depends on rob(i-1) and rob(i-2), can we fill in the answers iteratively from left to right?

Approach 3: Tabulation (Bottom-Up DP)

Intuition

Instead of starting from the end and recursing backward, we flip the direction. Start from the first house and work forward. For each house i, compute the best we can do considering houses 0 through i. The recurrence is the same: dp[i] = max(dp[i-1], nums[i] + dp[i-2]). But now we fill the table iteratively, which eliminates recursion overhead and makes the computation order explicit.

This is the classic bottom-up DP approach. It's often the version interviewers expect to see because it's clean, easy to analyze, and avoids any risk of stack overflow.

Algorithm

  1. If n == 1, return nums[0].
  2. Create an array dp of size n.
  3. Set dp[0] = nums[0] (only one house, rob it).
  4. Set dp[1] = max(nums[0], nums[1]) (pick the richer of the first two houses).
  5. For i from 2 to n-1: dp[i] = max(dp[i-1], nums[i] + dp[i-2]).
  6. Return dp[n-1].

Example Walkthrough

1Input: nums = [2, 7, 9, 3, 1]. Initialize dp array.
0
0
1
0
2
0
3
0
4
0
1/7

Code

We allocate an entire array of size n, but at any point we only ever look at the last two values. Can we replace the dp array with just two variables?

Approach 4: Space-Optimized DP

Intuition

Look at the recurrence again: dp[i] = max(dp[i-1], nums[i] + dp[i-2]). We only ever need two values from the past: the result one step back and the result two steps back. So instead of storing the entire dp array, we keep just two variables: prev1 (the best up to the previous house) and prev2 (the best up to two houses back).

As we move forward, we compute the new best, then shift the variables: the old prev1 becomes the new prev2, and the newly computed value becomes prev1. This brings space down from O(n) to O(1).

Algorithm

  1. If n == 1, return nums[0].
  2. Initialize prev2 = nums[0] and prev1 = max(nums[0], nums[1]).
  3. For i from 2 to n-1:
    • Compute current = max(prev1, nums[i] + prev2).
    • Update: prev2 = prev1, prev1 = current.
  4. Return prev1.

Example Walkthrough

1Input: nums = [2, 7, 9, 3, 1]. Initialize prev2=2, prev1=7
0
2
prev2=2
1
7
prev1=7
2
9
3
3
4
1
1/5

Code