Houses stand in a circle, and nums[i] is the money in house i. House i is next to houses
i − 1 and i + 1, and the last house is next to the first. Robbing two neighbouring houses
sets off an alarm.
Return the largest total you can take without robbing two neighbours. When there is only one house, you can rob it.
Example 1
- Input
- nums = [2, 3, 2]
- Output
- 3
Example 2
- Input
- nums = [1, 2, 3, 1]
- Output
- 4
Constraints
numsholds 1 to 2000 numbers.- 0 ≤
nums[i]≤ 1000
Show the pattern
Dynamic programming (1D)
Once you decide which end of the ring to leave alone, the circle becomes a straight row, and a straight row is solved by the one-dimensional rob-or-skip table.
See dynamic programming (1d) in a visualiserShow the approach
No safe choice robs both the first and the last house, so the best total is the better of two straight-row problems: houses 0 to n − 2 (the last house left alone) and houses 1 to n − 1 (the first house left alone).
Solve each row with the rob-or-skip walk: keep best, the most from the houses seen so far, and
before, the most from all but the last of them; at each house the new best is the larger of
best and before + money.
A single house is the exception: both rows would be empty, so return its money directly.
Time: O(n) · Space: O(1)