Every house on a street holds some money, and the alarm system trips if two adjacent houses are robbed on the same night. Given an integer array nums where nums[i] is the money in house i, return the most you can take without robbing two neighbours.
Examples
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: houses 0 and 2.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: houses 0, 2 and 4.
Example 3:
Input: nums = [2,1,1,2]
Output: 4
Explanation: the ends — sometimes the right move skips two houses, not one.
Example 4:
Input: nums = [5]
Output: 5
Constraints
1 <= nums.length <= 100
0 <= nums[i] <= 400
Prerequisites
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence. Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
How to think about it
1. Rob It or Skip It Optimal
Intuition
At each house there are exactly two futures: rob it, which forces skipping its neighbour and so builds on the best two houses back; or skip it, keeping the best from one house back. Carry both numbers forward and the street resolves in one pass. The greedy instinct — take every other house — is what [2,1,1,2] exists to break.
Algorithm
1. Track the best total that ends by robbing the current house, and the best that ends by skipping it. 2. Robbing now equals the skip-total from the previous house plus this money. 3. Skipping now equals the better of the two previous totals. 4. The answer is the better of the two at the end.