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
2class Solution {
3public:
4 int robLinear(vector<int>& nums, int start, int end) {
5 int prev1 = 0, prev2 = 0;
6 for (int i = start; i < end; i++) {
7 int temp = prev1;
8 prev1 = max(nums[i] + prev2, prev1);
9 prev2 = temp;
10 }
11 return prev1;
12 }
13 int rob(vector<int>& nums) {
14 int n = nums.size();
15 if (n == 1) return nums[0];
16 return max(robLinear(nums, 0, n - 1), robLinear(nums, 1, n));
17 }
18};
19This C++ solution uses a helper function robLinear for computing the linear house rob solution and applies it twice: once excluding the first house and once excluding the last house. It returns the maximum of these two 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
2public class Solution {
3 private Dictionary<int, int> memo = new Dictionary<int, int>();
4 private int RobHelper(int[] nums, int start, int end) {
5 if (start >= end) return 0;
6 if (memo.ContainsKey(start)) return memo[start];
7 int result = Math.Max(nums[start] + RobHelper(nums, start + 2, end), RobHelper(nums, start + 1, end));
8 memo[start] = result;
9 return result;
10 }
11
12 public int Rob(int[] nums) {
13 if (nums.Length == 1) return nums[0];
14 memo.Clear();
15 int case1 = RobHelper(nums, 0, nums.Length - 1);
16 memo.Clear();
17 int case2 = RobHelper(nums, 1, nums.Length);
18 return Math.Max(case1, case2);
19 }
20}
21This C# solution employs a Dictionary for managing memoization to store and retrieve calculated subproblems conveniently. The method RobHelper determines the maximum taking turns at each index, from which two scenarios for circle robbing are evaluated for the final yield optimum.