House Robber
Medium · dynamic programming
A street has a row of houses, and nums[i] is the amount of money hidden in house i. You can take the money from any houses you like, but the houses on this street share an alarm: if you take from two houses that are next to each other, it goes off.
Return the maximum total you can take without ever taking from two neighbouring houses. You may also skip houses freely, and taking nothing from a house with 0 in it is the same as taking it.
Examples
Example 1
Input: nums = [1, 2, 3, 1]
Output: 4
Take house 0 and house 2: 1 + 3 = 4. Taking houses 1 and 3 gives only 2 + 1 = 3.
Example 2
Input: nums = [2, 7, 9, 3, 1]
Output: 12
Take houses 0, 2 and 4: 2 + 9 + 1 = 12.
Example 3
Input: nums = [5]
Output: 5
Constraints
- 1 <= len(nums) <= 100
- 0 <= nums[i] <= 1000