Dynamic programming · 1D

Medium · O(n) time · O(1) space

Problem

You are a robber planning to rob houses along a street. Each house i holds nums[i] dollars. Adjacent houses have a connected security system: if you rob two houses that are next to each other, the alarm goes off. Return the maximum amount you can rob without robbing two adjacent houses.
Example 1 Input: nums = [1, 2, 3, 1] Output: 4 (rob house 0 and house 2: 1 + 3) Example 2 Input: nums = [2, 7, 9, 3, 1] Output: 12 (rob houses 0, 2 and 4: 2 + 9 + 1)
Constraints 1 ≤ nums.length ≤ 100 0 ≤ nums[i] ≤ 400

Brute force

Picture a street of houses in a row. Each house has some money inside. You may rob any houses you like, but if you rob two houses that stand next to each other, the alarm goes off. How much can you take?

  1. Each house holds a known amount of money.
  2. You cannot rob two neighbouring houses.
  3. Return the largest total you can take.

The direct idea: stand at the first house and make a choice. Either rob it and jump two houses ahead (the next house is off limits), or skip it and move one house ahead. Try both, and keep the better total.

The problem with it

Every house splits the search in two, so n houses give about 2n paths. It also repeats itself: "what is the best I can do from house 5 onwards?" is asked again from every path that reaches house 5, and the answer is always the same.

How to think your way to the optimal solution

The same small question keeps coming back: "what is the best total using only the first few houses?" So let us answer it once for each house, going from left to right, and write the answers down. If we know the best totals for the earlier houses, what is the best total up to this house?

Let dp[i] be the best total using houses 0 to i. At house i there are only two choices:

We take the bigger of the two. That is the whole idea: dp[i] = max(dp[i − 1], dp[i − 2] + nums[i]). The first two cells are special: dp[0] is the first house, and dp[1] is the larger of the first two houses, because we can only rob one of them.

The optimal solution

Approach 1: a table

  1. If there is only one house, rob it.
  2. Set dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).
  3. For each later house i: skip = dp[i − 1] and take = dp[i − 2] + nums[i].
  4. take is bigger⟶rob it: dp[i] = take otherwise⟶skip it: dp[i] = skip
  5. The answer is the last cell.

By hand, with houses [2, 7, 9, 3, 1]:

  1. dp[0] = 2. One house: rob it.
  2. dp[1] = 7. Two houses, pick the larger: 7.
  3. House 2 (9). Skip gives 7. Rob gives 2 + 9 = 11. Take the 11.
  4. House 3 (3). Skip gives 11. Rob gives 7 + 3 = 10. Skip is better, so it stays 11.
  5. House 4 (1). Skip gives 11. Rob gives 11 + 1 = 12. Take the 12.

The answer is 12: houses 0, 2 and 4. Press Play to watch the table fill, with the two values it compares at each house.

Approach 2: two numbers

The idea. Look at what each cell reads: only the one before it and the one two before it. Older cells are never looked at again. So we do not need the whole table. Two variables are enough: prev1 (the best up to the previous house) and prev2 (the best up to the house before that).

  1. Start both at 0, as if there were no houses.
  2. For each house with money x: the new best is max(prev1, prev2 + x). Then shift: prev2 becomes the old prev1.
  3. The answer is prev1.

By hand, [2, 7, 9, 3, 1], showing (prev2, prev1) after each house: house 2 gives (0, 2). House 7 gives (2, 7). House 9 gives (7, 11). House 3 gives (11, 11). House 1 gives (11, 12). The answer is the last prev1, 12.

Cost. Same time, but only two numbers of memory.

Complexity analysis

ApproachTimeSpace
Try every choice2nO(n)
A tableO(n)O(n)
Two numbersO(n)O(1)
O(n)
Time. Here's why: we visit each house once, and at each house we do one comparison and one addition. That takes the same small time for every house.
O(1)
Space (two numbers). Two variables, no matter how many houses. The table version uses O(n) because it stores one number per house.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"The street is a circle. The last house is next to the first."

What they are checkingWhether you can reuse your solution on a changed problem instead of starting again. This is the well-known "House Robber II".

A strong answerNow the first and last house cannot both be robbed. So any good plan leaves out at least one of them. I run my normal solution twice: once on houses 0 to n − 2 (without the last), and once on houses 1 to n − 1 (without the first). The answer is the larger of the two. With a single house, I just return it, because there is nothing to leave out.

"The houses are on a tree: you cannot rob a house and its direct children."

What they are checkingWhether you understood the two-choice idea (rob or skip), or only the list version of it.

A strong answerIt is the same two choices, but at each house in a tree. I visit the children first, then the house. Each house reports two numbers: the best total if I rob it (its money, plus the "skipped" totals of both children), and the best total if I skip it (the better of each child's two totals, added up). The answer is the larger of the two numbers at the root.

"Tell me which houses to rob, not only the total."

What they are checkingWhether you can read the answer back out of a table.

A strong answerI need the table, so I use Approach 1. I start at the last house. If dp[i] equals dp[i − 1], then skipping was at least as good, so I skip house i and move to i − 1. Otherwise I robbed it: I write down house i and jump to i − 2. I repeat until I run out of houses. The two-number version cannot do this, because it forgets the older cells.

Spot this pattern