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
2def robLinear(nums):
3 prev1, prev2 = 0, 0
4 for num in nums:
5 temp = prev1
6 prev1 = max(num + prev2, prev1)
7 prev2 = temp
8 return prev1
9
10class Solution:
11 def rob(self, nums):
12 if len(nums) == 1:
13 return nums[0]
14 return max(robLinear(nums[:-1]), robLinear(nums[1:]))
15This Python solution utilizes a helper function robLinear to handle the linear robbery problem. It then applies this helper to the range excluding first and last houses respectively, returning the greatest result.
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
2#include <string.h>
3
4int memo[101];
5
6int robLinearMemo(int* nums, int start, int end) {
7 memset(memo, -1, sizeof(memo));
8 return robHelper(nums, start, end);
9}
10
11int robHelper(int* nums, int start, int end) {
12 if (start >= end) return 0;
13 if (memo[start] >= 0) return memo[start];
14 memo[start] = (nums[start] + robHelper(nums, start + 2, end) > robHelper(nums, start + 1, end))
15 ? nums[start] + robHelper(nums, start + 2, end) : robHelper(nums, start + 1, end);
16 return memo[start];
17}
18
19int rob(int* nums, int numsSize) {
20 if (numsSize == 1) return nums[0];
21 int case1 = robLinearMemo(nums, 0, numsSize - 1);
22 int case2 = robLinearMemo(nums, 1, numsSize);
23 return (case1 > case2) ? case1 : case2;
24}
25The C solution sets up a memo array for memoization to store calculated maximums for each house start index. It runs the helper function robHelper which recursively looks for the maximum stealing options, caching results for efficiency. It applies this to the scenarios that exclude the first and last house respectively.