House Robber LeetCode Solution: Complete DP Walkthrough

If you have solved Climbing Stairs, you are closer to solving House Robber than you think. House Robber (#198) uses the exact same Fibonacci-style recurrence, but instead of counting ways to reach the top, you are maximizing the total money you can steal without triggering an alarm.

This is the problem that proves dynamic programming does not have to be scary. There are no 2D arrays, no complicated state transitions, and no confusing memoization tables. House Robber LeetCode boils down to one simple question at each step: do I take this house or skip it?

By the end of this walkthrough, you will understand the recurrence, build the bottom-up solution, and optimize it to O(1) space. More importantly, you will recognize a DP pattern that shows up in dozens of interview problems.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint is that adjacent houses have connected security systems — if you rob two houses next to each other, the alarm goes off.

Given an integer array nums where nums[i] represents the money at house i, return the maximum amount you can rob without alerting the police. That is the entire problem statement for LeetCode 198.

The key insight is that this is not a greedy problem. You cannot simply pick every other house or always grab the largest value. Consider [2, 7, 9, 3, 1]. Robbing houses 0, 2, and 4 gives you 2 + 9 + 1 = 12, but robbing houses 1 and 2... wait, those are adjacent. The optimal answer is houses 0 and 2: 2 + 9 = 11? No — it is actually 7 + 3 = 10 from houses 1 and 3, or 2 + 9 + 1 = 12 from houses 0, 2, and 4.

At every house, you have exactly two choices. You can skip it and keep whatever you had from the previous house. Or you can rob it and add its value to whatever you had two houses back (since you cannot rob the adjacent one). This gives us the house robber DP recurrence.

The recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]). If you skip house i, you take dp[i-1] because your best total is unchanged. If you rob house i, you take dp[i-2] + nums[i] because the last house you could have robbed is two steps back.

This is identical in structure to the Climbing Stairs recurrence f(n) = f(n-1) + f(n-2), except instead of adding the two previous values, you are taking the maximum. The Fibonacci dp pattern appears whenever you make a binary decision at each step and only need the last two results.

The bottom-up approach builds a dp array from left to right. You start with two base cases: dp[0] = nums[0] (if there is only one house, rob it) and dp[1] = max(nums[0], nums[1]) (if there are two houses, rob the richer one).

From index 2 onward, apply the recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]). When you reach the end of the array, dp[n-1] holds the answer. This runs in O(n) time and O(n) space.

Walk through the example [2, 7, 9, 3, 1]. dp[0] = 2. dp[1] = max(2, 7) = 7. dp[2] = max(7, 2 + 9) = 11. dp[3] = max(11, 7 + 3) = 11. dp[4] = max(11, 11 + 1) = 12. The answer is 12, which comes from robbing houses 0, 2, and 4.

Look at the recurrence again: dp[i] only depends on dp[i-1] and dp[i-2]. You never look further back than two steps. That means you do not need the entire dp array — just two variables.

Replace the array with prev2 (representing dp[i-2]) and prev1 (representing dp[i-1]). At each step, compute the current value as max(prev1, prev2 + nums[i]), then shift the variables forward. This drops space from O(n) to O(1) while keeping O(n) time.

This house robber space optimization is identical to how you optimize Climbing Stairs. Whenever a DP recurrence only references a fixed number of previous states, you can replace the array with that many variables. It is one of the most common interview follow-up questions.

The edge cases for House Robber are straightforward. If there is only one house, return nums[0]. If there are two houses, return max(nums[0], nums[1]). If all houses have the same value, you rob every other house. These are all handled by the base cases in the bottom-up approach.

House Robber II (#213) adds a circular constraint — the first and last houses are now adjacent. You solve it by running House Robber twice: once on nums[0..n-2] (exclude the last house) and once on nums[1..n-1] (exclude the first house), then taking the max of both results.

House Robber III (#337) takes the problem to a binary tree. Each node has a value, and you cannot rob directly connected nodes. The recurrence becomes: for each node, either rob it and skip its children, or skip it and take the best from its children. This uses DFS with memoization.

House Robber is the perfect introduction to the take-or-skip DP pattern. At every step, you make a binary choice — include this element or exclude it — and the recurrence captures both options. This same pattern appears in Climbing Stairs, Delete and Earn (#740), and dozens of knapsack-style problems.

The progression from brute-force recursion to memoization to bottom-up tabulation to space-optimized variables is the core DP workflow. House Robber lets you practice all four stages on a problem simple enough that you can hold the entire state in your head.

If you want to lock in the house robber explained pattern and its variants, YeetCode flashcards break it down into bite-sized reviews. Drill the recurrence, the base cases, and the space optimization until they become automatic — so when the interviewer throws a twist at you, you are ready.