House Robber

The problem

nums[i] is the money in house i of a street. A robber may take the money of any houses, as long as no two of them are next to each other. Return the largest total the robber can take. If the street has no houses, return 0.

What to write

function solve(nums: number[]): number

Input
nums = [1,2,3,1]

Output
4

Input
nums = [2,7,9,3,1]

Output
12

Constraints

0–10,000 nonnegative integer values.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 10,000 houses, far too many to try every set of houses. A fixed rule such as every second house is not enough either: in [2, 1, 1, 2] the best plan takes the first and the last house and skips two in a row.

2. Hint 2: Ask a smaller question

   Stand in front of the last house of [2, 7, 9, 3, 1]. Either you rob it or you leave it. In each case, which of the houses before it are you still free to choose from?

3. Hint 3: Name the pattern

   The best total for the first few houses comes from two shorter streets: leave the last of those houses and keep the best total without it, or rob it and add the best total that stops two houses earlier. Building each answer from earlier answers like this is one-dimensional dynamic programming. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   Before each house you hold two totals: the best for all the houses before it, and the best for those houses without the last one. Skipping the house keeps the first total. Robbing it adds its money to the second. The larger of the two is the best total up to this house.

5. Hint 5: Sketch the pseudocode

   previous = 0, current = 0. For each amount in nums: best = the larger of current and previous + amount; then previous = current and current = best. Return current.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

For each house compare skipping it with taking its value plus the best total two houses back. Keep only the two preceding totals.

The slow way

Try every set of houses, throw away the sets that hold two neighbors, and keep the largest total. It is correct, but every extra house doubles the number of sets. 20 houses already give 1,048,576 sets, and the street can have 10,000 houses.

The insight

Go along the street and ask one question per house: what is the best total using only the houses up to here? There are two choices. Skip this house and keep the best total so far. Or rob it, which rules out the house right before it, and add its money to the best total from two houses back.

Step by step

1. Before the first house, the best total is 0. Two totals are kept: the best up to the previous house, and the best up to the house before that. With no houses seen, both are 0, which is also the answer for an empty street.
2. Go along the street one house at a time. The best total up to a house depends only on the best totals up to the two houses before it. So one walk along the street, building each total once from earlier ones, is enough: dynamic programming again.
3. Take the larger of skipping this house and robbing it. Skipping keeps the best total up to the previous house. Robbing adds this house's money to the best total up to two houses back, because the house right before it must then be left alone.
4. Keep only the two newest totals. The next house needs the best total up to this house and the best up to the one before it. Anything older is never read again.
5. Return the newest total, the best for the whole street. After the last house the newest total covers every house. From house to house it can only stay the same or grow, since skipping is always allowed.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Before the first house, the best total is 0
  let previous = 0;
  let current = 0;
  // 2. Go along the street one house at a time
  for (const money of nums) {
    // 3. Take the larger of skipping this house and robbing it
    const best = Math.max(current, previous + money);
    // 4. Keep only the two newest totals
    previous = current;
    current = best;
  }
  // 5. Return the newest total, the best for the whole street
  return current;
}

function solve(nums: number[]): number {
  // 1. Before the first house, the best total is 0
  let previous = 0;
  let current = 0;
  // 2. Go along the street one house at a time
  for (const money of nums) {
    // 3. Take the larger of skipping this house and robbing it
    const best = Math.max(current, previous + money);
    // 4. Keep only the two newest totals
    previous = current;
    current = best;
  }
  // 5. Return the newest total, the best for the whole street
  return current;
}

def solve(nums):
    # 1. Before the first house, the best total is 0
    previous = 0
    current = 0
    # 2. Go along the street one house at a time
    for money in nums:
        # 3. Take the larger of skipping this house and robbing it
        best = max(current, previous + money)
        # 4. Keep only the two newest totals
        previous = current
        current = best
    # 5. Return the newest total, the best for the whole street
    return current

Example 2, traced

Input
nums = [2,7,9,3,1]

Output
12

Why it works

After each house, the newest total is the best possible for the houses up to that one. Any plan for those houses either leaves the last one out, and then cannot beat the best total before it, or robs it, and then cannot beat the best total from two houses back plus its money. The method takes the larger of the two.

Time and space

Time O(n), extra space O(1). The loop visits each of the n houses once and does one addition and one comparison there, so the time is O(n). Only two totals are kept, however long the street is, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Rob on top of the total from two houses back, not the newest total. The newest total may already include the house next door, and adding to it takes every house: example 1 gives 7 instead of 4.
• Keep the choice to skip. Always adding to the total from two houses back gives 3 for [2, 1, 1, 2], where the best plan skips two houses in a row and takes 4.
• Start both totals at 0 instead of reading the first house up front. Code that begins with the money of the first one or two houses goes wrong on an empty street, where the answer is 0.

Pattern

One-dimensional dynamic programming. Builds on Min Cost Climbing Stairs.

Keep going