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)
Restating the Problem: Imagine you are walking down a street with a bag, and you want to stuff as much cash in it as possible. The only rule is that the local neighborhood watch is set up so that if two neighboring houses are robbed on the same night, the alarm triggers. Thus, you must never pick two adjacent houses in the array. Your goal is to maximize your total loot without setting off the alarm.
Constraints to Note:
The array can have up to 100 houses, which means anything slower than O(N^2) (like an exponential O(2^N) brute force) is going to fail on larger test cases.
A house can have 0 money.
The array can be empty or have just 1 house (we must handle these edge cases gracefully).
The most naive way to solve this is to just try every valid combination of houses. For every house, we branch into two universes: one where we rob it (and skip the next), and one where we skip it (and move to the next).
Since every house presents up to two choices, the recursion tree grows exponentially, giving a time complexity of O(2^N). With N = 100 houses, 2^{100} operations would take longer than the age of the universe to compute. The massive waste here is that we end up solving the exact same subproblems (e.g., "what's the max profit from house 5 onwards?") repeatedly. We need to eliminate this overlapping work.
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.
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.
Think of it like being a picky eater at a buffet where eating one dish means you are too full to eat the dish right next to it. For every dish, you look at it and ask yourself: "Is the joy of eating this dish plus the joy from everything I ate before the previous dish greater than if I just skip this one and keep my total joy from the previous dish?" The choice at step i only depends on the optimal choices made at i-1 and i-2.
class Solution: def rob(self, nums: List[int]) -> int: two, one = 0, 0 # (1) dp[i-2], dp[i-1] for n in nums: # (2) two, one = one, max(n + two, one) # (3) return one # (4)
ts
function rob(nums: number[]): number { let two = 0, one = 0; // (1) dp[i-2], dp[i-1] for (const n of nums) { // (2) [two, one] = [one, Math.max(n + two, one)]; // (3) } return one; // (4)}
(1) one is the best total for the houses up to the previous one, and two is the best total for the houses up to the one before that. Before any house, both are 0.
(2) Visit each house in order.n is the money in this house.
(3) Decide about this house.
n + two means rob it. Then the previous house must be skipped, so we add this money to the best total from two houses back.
one means skip it, and keep the best total from the previous house.
The larger of the two is the best total up to this house. Then everything slides forward by one house: the old one becomes two, and the new best becomes one. Both are assigned together, so two is read before it is overwritten.
(4) After the last house, one is the best total for the whole street.
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:
One house. One step of the loop gives max(n + 0, 0) = n.
Two houses. You can only rob one, the richer. The loop gives exactly that.
All houses empty. The answer is 0.
The best plan skips two houses in a row, like [2, 1, 1, 2]. The answer is 4, from the first and last. The recurrence finds it, because skipping is always one of the two choices.
Time Complexity Derivation: We loop through the array of n houses exactly once. Inside the loop, we are just doing constant-time operations (addition, max(), and simple variable reassignment). So, we do O(1) work N times, giving a total time complexity of O(N).
Space Complexity Derivation: Even though the theoretical DP table would be of size N (giving O(N) space), we noticed that we only ever look back exactly two steps (dp[i-1] and dp[i-2]). By just keeping track of those two previous values using rob_prev and skip_prev, we avoid allocating an array. Storing two integer variables takes O(1) extra memory.
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.
"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.