You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums
representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3] Output: 3
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
This problem extends the classic "House Robber" problem by arranging the houses in a circle. This means the first and last houses are adjacent, and we cannot rob both. We can solve this by breaking it down into two subproblems:
The maximum amount of money we can rob is the maximum of the results from these two subproblems.
The core idea is to use dynamic programming to efficiently solve the standard House Robber problem for each subproblem. We can use two variables to track the maximum amount of money we can rob up to a given point.
f
: Represents the maximum money robbed excluding the current house.g
: Represents the maximum money robbed including the current house.For each house, we update f
and g
as follows:
f
becomes the maximum of the previous f
and g
(we either include or exclude the previous house).g
becomes the previous f
plus the current house's value (we include the current house).After iterating through all houses, the maximum amount we can rob is max(f, g)
.
Time Complexity: O(n), where n is the number of houses. We iterate through the array of house values twice (once for each subproblem). The dynamic programming step within each iteration is constant time.
Space Complexity: O(1). We only use a few constant-size variables (f
and g
) to store the intermediate results. We don't use any auxiliary data structures that scale with the input size.
The code implementations below follow the dynamic programming approach. They first define a helper function _rob
or robRange
that solves the standard House Robber problem. Then, the main rob
function calls this helper function twice, once for each subproblem, and returns the maximum of the two results.
Python:
class Solution:
def rob(self, nums: List[int]) -> int:
def _rob(nums):
f = g = 0
for x in nums:
f, g = max(f, g), f + x
return max(f, g)
if len(nums) == 1:
return nums[0]
return max(_rob(nums[1:]), _rob(nums[:-1]))
Java:
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
private int robRange(int[] nums, int l, int r) {
int f = 0, g = 0;
for (; l <= r; ++l) {
int ff = Math.max(f, g);
g = f + nums[l];
f = ff;
}
return Math.max(f, g);
}
}
C++, Go, TypeScript, and Rust implementations are provided in the original response and follow the same logic, adapting the syntax and data structures to the specific language. The core dynamic programming algorithm remains consistent across all implementations.