House Robber
MediumDynamic Programming
Houses stand in a straight line, and nums[i] is the amount of money in house i. You may rob any set of houses, but you can never rob two houses that are next to each other.
Return the largest total amount of money you can rob.
Example 1
- Input:
- nums = [5, 1, 2, 10, 6]
- Output:
- 15
- Explanation
- Rob houses 0 and 3 for 5 + 10 = 15. Alternating picks (5 + 2 + 6 = 13) is worse, so sometimes it pays to skip two houses in a row.
Example 2
- Input:
- nums = [8, 3, 7, 3, 8]
- Output:
- 23
- Explanation
- Rob houses 0, 2 and 4 for 8 + 7 + 8 = 23. None of them are adjacent.
Example 3
- Input:
- nums = [5]
- Output:
- 5
- Explanation
- With one house, rob it.
Constraints
- 1 ≤
nums.length≤ 100 - 0 ≤
nums[i]≤ 400