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)); }};