A street has a row of houses, and nums[i] is the amount of money in house i. You may rob any
houses you like, except that robbing two houses that stand next to each other sets off an alarm.
Return the largest total you can take without robbing two neighbouring houses.
Example 1
- Input
- nums = [2, 7, 9, 3, 1]
- Output
- 12
Example 2
- Input
- nums = [5, 1, 1, 5]
- Output
- 10
Constraints
numsholds 1 to 2000 numbers.- 0 ≤
nums[i]≤ 1000
Show the pattern
Dynamic programming (1D)
At each house you either rob it, adding to the best total from two houses back, or skip it and keep the best total so far. Each answer builds from the two before it: a one-dimensional table.
See dynamic programming (1d) in a visualiserShow the approach
Walk along the street keeping two numbers: best, the most you can take from the houses seen so
far, and before, the most you can take from all of them but the last.
At a house holding money, robbing it gives before + money (its neighbour on the left must be
skipped, and before already leaves it out); skipping it keeps best. The new best is the
larger of the two, and the old best becomes before. After the last house, best is the
answer.
Time: O(n) · Space: O(1)