House Robber
Medium· 1D DP
Problem
A row of houses each holds some amount of money. You may take money from any set of houses as long as no two chosen houses are next to each other. Return the largest total you can collect.
Examples
Input: nums = [1,2,3,1]
Output: 4
Take houses 0 and 2: 1 + 3.
Input: nums = [2,7,9,3,1]
Output: 12
Take houses 0, 2 and 4: 2 + 9 + 1.
Constraints
- • 1 <= nums.length <= 100
- • 0 <= nums[i] <= 400
Hints & approach
Hint 1
For each house you make a binary choice: take it or skip it.
Hint 2
If you take house i, the best you could have before it is the answer for i-2.
Hint 3
best[i] = max(best[i-1], best[i-2] + nums[i]).
Approachtry the hints first
Let best[i] be the most money obtainable from the first i houses. For house i, either skip it (best[i-1]) or take it and add it to best[i-2], since its neighbour is off-limits. Base cases are best[0] = 0 and best[1] = nums[0]. Rolling two variables through the array gives the answer in one pass.
Time O(n) · Space O(1)