Houses are arranged in a circle, so the first and the last house are neighbours. You cannot rob two adjacent houses, so return the most money you can rob.
DSA Animator › DSA Revision › Dynamic Programming › House Robber II
Remember: break a circle by solving two lines, each excluding one end. Then reuse the linear solution. The video solves House Robber II (LeetCode 213, Medium) with the Circular 1D DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive House Robber II animation.
Houses are arranged in a circle, so the first and the last house are neighbours. You cannot rob two adjacent houses, so return the most money you can rob.
For the houses 2, 7, 9, 3, 1, the answer is 11, by robbing 2 and 9.
Trying every subset of houses that are not adjacent is exponential. The circle is the only new difficulty compared with House Robber 1.
The first and the last house can never both be robbed. So solve two straight line problems. One skips the last house, and the other skips the first house. For each line, use the House Robber rule: the best up to house i is the larger of skipping it, or robbing it plus the best up to i minus 2. The answer is the larger of the two results.
Case one uses houses 2, 7, 9, 3. The best values grow 2, 7, 11, 11, so this case gives 11. Case two uses houses 7, 9, 3, 1. The best values grow 7, 9, 10, 10, so this case gives 10. The larger result is 11. It comes from robbing 2 and 9.
In code, handle a single house separately. Write a helper that runs the linear robber on a range, with two rolling variables. Return the maximum of the helper on 0 to n minus 2 and on 1 to n minus 1. It's O of n time and O of 1 space.
Remember: break a circle by solving two lines, each excluding one end. Then reuse the linear solution.