πŸ“ Problem Details

πŸ’­What Were My Initial Thoughts?

1. Subproblem
	- houses are in a circle, so nums[0] and nums[n-1] cannot both be robbed
	- solve twice
	1. rob from nums[0] to nums[n-2]
	2. rob from nums[1] to nums[n-1]
	- take the max of both

2. Top-down vs. Bottom-up
	- bottom up is best, solving each case separately
	- top down with recursion is possible but inefficient

3. Define DP state
	- dp[i] stores the max money robbed up to house i in the chosen range

4. Transition formula
	- same as House Robber I
	- dp[i] = max(dp[i-1], dp[i-2] + nums[i])
	- apply it to two separate cases

5. Optimize Space
- Same as House Robber 1: keep only last two values (O(1) space)
- Can still use a full DP table (O(n) space) for learning

βŒ› Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n) but can be optimized to O(1)

πŸ’» Implementation of Solution

class Solution {
public:
    int robWithDP(vector<int>& nums, int start, int end) {
        int n = end - start + 1;
        if (n == 1) return nums[start];
 
        vector<int> dp(n, 0);
        dp[0] = nums[start];
        dp[1] = max(nums[start], nums[start + 1]);
 
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[start + i]);
        }
 
        return dp[n-1];
    }
 
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
 
        return max(robWithDP(nums, 0, n-2), robWithDP(nums, 1, n-1));
    }
};