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
2public class Solution {
3 private int RobLinear(int[] nums, int start, int end) {
4 int prev1 = 0, prev2 = 0;
5 for (int i = start; i < end; i++) {
6 int temp = prev1;
7 prev1 = Math.Max(nums[i] + prev2, prev1);
8 prev2 = temp;
9 }
10 return prev1;
11 }
12
13 public int Rob(int[] nums) {
14 if (nums.Length == 1) return nums[0];
15 return Math.Max(RobLinear(nums, 0, nums.Length - 1), RobLinear(nums, 1, nums.Length));
16 }
17}
18This C# solution defines RobLinear for the linear version of the problem and solves it for two cases: one excluding the first and another excluding the last house. The maximum of these two outcomes is returned.
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
2var robHelper = function(nums, start, end, memo) {
3 if (start >= end) return 0;
4 if (memo[start] !== undefined) return memo[start];
5 memo[start] = Math.max(nums[start] + robHelper(nums, start + 2, end, memo), robHelper(nums, start + 1, end, memo));
6 return memo[start];
7};
8
9var rob = function(nums) {
10 if (nums.length === 1) return nums[0];
11 const memo1 = {};
12 const memo2 = {};
13 return Math.max(robHelper(nums, 0, nums.length - 1, memo1), robHelper(nums, 1, nums.length, memo2));
14};
15This JavaScript solution applies memoization utilizing plain objects to store precomputed solutions. The function robHelper determines the best regular house rob outcomes recursively while updating cache objects accordingly for each scenario considered.