Same as House Robber, but now the houses stand in a circle: the first and the last house are neighbours. Given nums, the money in each house, return the most you can rob without robbing two adjacent houses.
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force checks all valid subsets on the circle, O(2^n). The circle only adds one constraint: house 0 and house n - 1 cannot both be robbed. Split into two cases. Case 1 skips the last house, so the rest is a normal line 0..n-2. Case 2 skips the first house, a line 1..n-1. Each case is the linear DP dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) with base dp = 0 before the first house. The answer is the max of both. With one house there is nothing to conflict, so return nums[0].
Algorithm
- If there is only one house, return
nums[0]. - Write a helper that runs linear House Robber on a range
[lo, hi]with two rolling variables. - Compute
a = helper(0, n - 2)andb = helper(1, n - 1). - Return
max(a, b).
O(n)Space: O(1)nums[0]. A good follow-up is House Robber III, where the houses form a binary tree.class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n == 1: return nums[0]Β def rob_line(lo, hi): # linear House Robber on nums[lo..hi] prev2, prev1 = 0, 0 for i in range(lo, hi + 1): prev2, prev1 = prev1, max(prev1, prev2 + nums[i]) return prev1Β # either skip the last house or skip the first house return max(rob_line(0, n - 2), rob_line(1, n - 1))