This approach involves splitting the problem into two scenarios: robbing from house 0 to house n-2, and from house 1 to house n-1. The aim is to apply the linear version of the House Robber problem to each scenario separately and then take the maximum of the two resulting summed values.
Time Complexity: O(n).
Space Complexity: O(1).
1
2int robLinear(int* nums, int len) {
3 if (len == 0) return 0;
4 if (len == 1) return nums[0];
5 int prev1 = 0, prev2 = 0;
6 for (int i = 0; i < len; i++) {
7 int temp = prev1;
8 prev1 = (nums[i] + prev2 > prev1) ? nums[i] + prev2 : prev1;
9 prev2 = temp;
10 }
11 return prev1;
12}
13
14int rob(int* nums, int numsSize) {
15 if (numsSize == 1) return nums[0];
16 return (robLinear(nums, numsSize - 1) > robLinear(nums + 1, numsSize - 1))
17 ? robLinear(nums, numsSize - 1)
18 : robLinear(nums + 1, numsSize - 1);
19}
20This C solution defines a helper function robLinear for the simpler linear version of the House Robber problem, then uses this to calculate the maximum rob amount in two scenarios: excluding the first and last house respectively. The final result is the maximum of these two computed values.
This approach implements a memoized version of the dynamic programming solution to avoid recomputing values. We explore two scenarios of the circle, taking into account the cycles explicitly by caching intermediate results.
Time Complexity: O(n).
Space Complexity: O(n) for the memoization array.
1
2class Solution:
3 def robHelper(self, nums, start, end, memo):
4 if start >= end:
5 return 0
6 if memo[start] >= 0:
7 return memo[start]
8 memo[start] = max(nums[start] + self.robHelper(nums, start + 2, end, memo), self.robHelper(nums, start + 1, end, memo))
9 return memo[start]
10
11 def rob(self, nums):
12 if len(nums) == 1:
13 return nums[0]
14 memo1 = [-1] * len(nums)
15 memo2 = [-1] * len(nums)
16 return max(self.robHelper(nums, 0, len(nums) - 1, memo1), self.robHelper(nums, 1, len(nums), memo2))
17This Python solution makes use of a memo array to store intermediate maximums to prevent redundant calculations. The robHelper function recursively determines possible rob outcomes and updates the cache, providing two results depending on whether the first house is considered or not.