House Robber

Q: What is the recurrence for House Robber?

The best total from the first k houses is max(best[k-1], best[k-2] + nums[k-1]) . You either skip house k-1 and keep the best from the houses before it, or take house k-1 and add it to the best that ends before its neighbor. The base cases are 0 for no houses and nums[0] for one house.

Q: Why doesn't taking every other house solve House Robber?

The best plan sometimes skips two houses in a row. In [10, 1, 1, 10] the even houses and the odd houses both sum to 11, while taking the first and the last house gives 20. Dynamic programming compares skipping and taking at every house, so it finds those plans.

MediumDynamic programming

+10

Houses stand in a row along a street, and nums[i] is the money in house i. You may take the money from any houses you choose, but never from two houses that stand next to each other. Return the largest total you can take.

Function

rob(nums: integer-array) → integer

numsinteger-array: the money in each house, in street order
Returnsinteger: the largest total you can take without taking from two adjacent houses

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
The answer is at most 5 × 10⁶, so it fits in a signed 32-bit integer.

Examples

Input: nums = [5, 3, 4, 11, 2]
Output: 16
Explanation: Take 5 and 11 from houses 0 and 3 for 16. Skipping two houses in a row is allowed, and here it beats every other plan: 5 + 4 + 2 = 11 and 3 + 11 = 14.

+16 hidden tests on Submit

Follow-up

Return the houses to take as well as the total. What do you have to keep from the table to rebuild that list, and can the two running totals still do it?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The obvious shortcuts fail. Taking every other house misses plans that skip two houses in a row, like 5 and 11 in [5, 3, 4, 11, 2], and taking the richest house first fails on [3, 4, 3], where 4 blocks two houses worth 6 together. What works is deciding 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.

Try both choices at every house

Correct, but does not finish on the largest tests

Intuition

Look at the last house, house n-1. Any plan either skips it or takes it. If it skips it, the best it can do is the best plan for the first n-1 houses. If it takes it, house n-2 is off limits, so it adds nums[n-1] to the best plan for the first n-2 houses. The answer is the larger of the two.

Write that as a function most(k), the most you can take from the first k houses: most(k) = max(most(k-1), most(k-2) + nums[k-1]), with most(0) = 0 for no houses and most(1) = nums[0] for one. Every plan skips or takes its last house, so the two branches cover every plan and the result is correct.

It is slow because the branches overlap. most(k-1) calls most(k-2) again, so the same question is answered over and over, and the number of calls grows like the Fibonacci numbers, about 1.6^n. Forty houses already take over 300 million calls, and the tests have up to 10^4 houses. The calls also nest n levels deep, past Python's default limit of 1000.

Algorithm

Write a helper most(k) that returns the most you can take from the first k houses.
Return 0 when k is 0, and nums[0] when k is 1.
Otherwise work out skip = most(k-1) and take = most(k-2) + nums[k-1].
Return the larger of the two. The answer is most(n).

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

Bottom-up table

Intuition

The recursion only ever asks about most(0) through most(n), so there are n + 1 different questions. Answer each one once, store it in a table, and fill the table in an order where every answer you read is already there. Four decisions define the table.

State: best[k] is the most you can take from the first k houses. Recurrence: best[k] = max(best[k-1], best[k-2] + nums[k-1]): skip house k-1, or take it on top of the best that ends before its neighbor. Base cases: best[0] = 0 and best[1] = nums[0]. Order: k from 2 up to n, because each entry reads the two entries before it.

For [5, 3, 4, 11, 2] the table is 0, 5, 5, 9, 16, 16. At k = 4 you compare skipping house 3, worth best[3] = 9, with taking its 11 on top of best[2] = 5, and 16 wins. The answer is the last entry. Each entry costs one comparison, so the time is O(n), and the table takes O(n) space.

Algorithm

Make a table best with n + 1 entries.
Set best[0] = 0 and best[1] = nums[0].
For k from 2 to n, set best[k] to the larger of best[k-1] and best[k-2] + nums[k-1].
Return best[n].

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

Two running totals

Intuition

Each entry of the table reads only the two entries right before it. Once best[k] is known, best[k-2] is never read again. So keep two numbers instead of the table: twoBack, the best total from the houses up to two steps back, and oneBack, the best total up to the previous house.

For a house holding x, the new best is max(oneBack, twoBack + x). Then shift: twoBack takes the old oneBack, and oneBack takes the new best. Both start at 0, which stands for the empty street before the first house, so the first house needs no special case: its best is max(0, 0 + nums[0]).

On [5, 3, 4, 11, 2] the pair goes (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), and oneBack ends at 16. The work is the same O(n) as the table, and the memory drops to O(1).

Algorithm

Set twoBack and oneBack to 0.
For each amount x in nums, work out current = max(oneBack, twoBack + x).
Move oneBack into twoBack, then current into oneBack.
After the last house, return oneBack.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

Pitfalls and edge cases

Most wrong answers come from a shortcut that works on small inputs, or from updating the two totals in the wrong order.

Summing the even houses and the odd houses and taking the larger misses plans that skip two houses in a row. On [10, 1, 1, 10] both sums are 11, but houses 0 and 3 give 20.
Taking the richest house first fails on [3, 4, 3]: it takes 4 and blocks both 3s, which make 6 together.
Overwriting oneBack before you copy it into twoBack loses the value the next house needs. Work out the new best first, then shift, or assign both at once where the language allows it.
Reading nums[1] or setting best[1] and best[2] up front breaks on a street with one house. Starting both totals at 0 removes the special case.
In Lua and R, arrays start at 1, so the money in house k-1 is nums[k].

Frequently asked questions4

What is the recurrence for House Robber?

The best total from the first k houses is max(best[k-1], best[k-2] + nums[k-1]). You either skip house k-1 and keep the best from the houses before it, or take house k-1 and add it to the best that ends before its neighbor. The base cases are 0 for no houses and nums[0] for one house.

What is the time and space complexity of House Robber?

The dynamic programming solution looks at each house once, so it takes O(n) time. A full table uses O(n) space, and keeping only the last two totals brings that down to O(1). Plain recursion without stored answers makes about 1.6^n calls, which is exponential.

Why doesn't taking every other house solve House Robber?

The best plan sometimes skips two houses in a row. In [10, 1, 1, 10] the even houses and the odd houses both sum to 11, while taking the first and the last house gives 20. Dynamic programming compares skipping and taking at every house, so it finds those plans.

How do you solve House Robber when the houses form a circle?

In a circle the first and the last house are neighbors, so a plan can take at most one of them. Run the straight-street solution twice, once without the last house and once without the first, and return the larger result. A street with a single house is the one special case: the answer is that house.