Ring of houses
Rob houses around a circle with no two neighbours, where the first and last are neighbours too. About 12 minutes.
What changes on a ring?
On a straight row you chose, house by house, to rob it or skip it, never robbing two neighbours. On a ring, the last house sits next to the first, so you can never rob both of them.
Here is the useful question: if you know for sure the first house is skipped, what kind of problem is left? And what if you know the last one is skipped? Can the ring become rows you already know how to solve?
- case
- both ends possible
On the ring, house 0 and house 4 are neighbours, so you can't rob both. Split into two cases.
Why can't you just use the straight-row answer for a ring of houses?
- AThe first and last houses are neighbours, so the row answer might rob both
- BA ring has more houses than a row
- CYou may rob neighbours on a ring
Show the answer
The first and last houses are neighbours, so the row answer might rob both. On a ring every house has two neighbours, and the straight-row plan doesn't know the last touches the first.
Ring of houses
Houses stand in a circle, and house i holds nums[i] coins. The first and last houses are neighbours. You may rob any houses, but never two neighbours. Return the largest total you can collect.
nums = [2, 7, 9, 3, 1] → 11
1 ≤ length ≤ 300 · 0 ≤ nums[i] ≤ 1,000