House Robber II
House Robber II is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is dp on two ranges, and a good solution runs in O(n) time.
Problem
Return the maximum sum of non-adjacent house values when the first and last houses are adjacent in a circle.
Examples
Example 1
Input
[2,7,9,3,1]Output
11Example 2
Input
[4,6,4]Output
6Example 3
Input
[2,4,6,2]Output
8Approach
Houses form a circle, so the first and last cannot both be robbed. Run the straight-line solution once without the last house and once without the first, and take the better.
| Pattern | DP on two ranges |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
A single house is its own answer.