House Robber

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 the first and the last house give 20.

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.

Follow-up

Return the houses to take as well as the total. What must you keep from the table to rebuild that list, and can 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

Shortcuts fail: taking every other house misses 5 and 11 in [5, 3, 4, 11, 2], and taking the richest house first loses on [3, 4, 3]. Decide one house at a time instead: 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

Any plan either skips the last house or takes it. Skipping leaves the best plan for the first n-1 houses; taking adds nums[n-1] to the best plan for the first n-2. So most(k) = max(most(k-1), most(k-2) + nums[k-1]), with most(0) = 0 and most(1) = nums[0]. The two branches cover every plan, so the answer is correct.

The branches overlap: most(k-1) asks for most(k-2) again, and the number of calls grows like the Fibonacci numbers, about 1.6^n. Forty houses take over 300 million calls, and n reaches 10^4.

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 asks about most(0) through most(n): n + 1 questions. Answer each once in a table best, starting from best[0] = 0 and best[1] = nums[0] and filling upward from k = 2, so that the two entries each answer reads are already there.

For [5, 3, 4, 11, 2] the table is 0, 5, 5, 9, 16, 16. At k = 4, skipping house 3 keeps best[3] = 9, while taking its 11 on top of best[2] = 5 gives 16, which wins. Each entry costs one comparison: O(n) time and 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 reads only the two entries before it, so keep two numbers instead of the table: twoBack and oneBack, the best totals up to two houses back and up to the previous house. For a house holding x, the new best is max(oneBack, twoBack + x); then shift both along. Both start at 0, the empty street before the first house, so a street of one house needs no special case. Time stays O(n), and 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

Overwriting oneBack before copying it into twoBack. The next house then reads the wrong total. Compute the new best first, then shift, or assign both at once.
Reading nums[1], or setting best[1] and best[2] up front. Both break on a street of one house, such as [0].
In Lua and R, arrays start at 1, so the money in house k-1 is nums[k].

Frequently asked questions3

What is the time and space complexity of House Robber?

Dynamic programming 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.

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 the first and the last house give 20.

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 takes 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 single house is the special case: the answer is that house.