Sweaty Imposter

House Robber

MediumDynamic Programming (1-D & 2-D)Blind 75MidOpen on LeetCodeUpdated

You're given an integer array nums where nums[i] is the amount of money stashed in the i-th house on a street. You may take money from any set of houses, but never from two houses that sit next to each other, because neighboring houses share an alarm. Each house is either taken in full or skipped, and you may skip several houses in a row. Return the maximum total you can collect.

Examples

nums = [1,2,3,1] returns 4

1231
Highlighted houses are the ones taken: 1 + 3 = 4.

Take houses 0 and 2 for 1 + 3 = 4. The other pairs of non-neighbors, houses 0 and 3 or houses 1 and 3, collect only 2 or 3.

nums = [2,7,9,3,1] returns 12

Take houses 0, 2 and 4 for 2 + 9 + 1 = 12. Taking the 7 rules out both of its neighbors, and the best plan that uses it, 7 + 3, reaches only 10.

nums = [2,1,1,2] returns 4

2112
Skipping two neighbors in a row is allowed, and it wins here.

Take the first and last houses for 2 + 2 = 4, skipping two houses in a row. Taking every other house gives at most 3.

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Hints

Hint 1

Look at the last house. It's either part of the plan or it isn't, and each case leaves a shorter street to solve.

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Let best[i] be the most money you can collect from houses 0..i. At house i you either skip it and keep best[i-1], or take it and add nums[i] to best[i-2], because its left neighbor must then be skipped. Only the last two values are ever read, so two rolling variables replace the array. O(n) time, O(1) space.

Time

O(n)

Space

O(1)

Pitfall

Assuming the answer is the larger of the even-index sum and the odd-index sum. [2,1,1,2] breaks that: the best plan skips two houses in a row for 4, while both alternating sums give 3.

Solutions

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0; // best total through house i - 2
        int prev1 = 0; // best total through house i - 1
        for (int money : nums) {
            int cur = Math.max(prev1, prev2 + money);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}
Drill This