Problem Explanation

The robber wants to rob the houses in a way that he gets the maximum money. However, there are two constraints. The first constraint is that the houses are arranged in a circular manner which means the first house is the neighbor of the last one. The second constraint is due to the security system which contacts the police if two adjacent houses are broken into on the same night. We need to come up with a strategy that maximizes the total loot under these two constraints.

The main challenge of this problem is to handle the wrap-around adjacency. We need to decide whether rob the 1st house (making the last house unavailable) or to rob the last house (making the first house unavailable). This is based on the Robber I problem but the difference is in this problem houses are arranged in a circle which adds one more valid condition to it.

For instance, suppose we are given the amounts in each house as [1,2,3,1]. The optimal solution would be to rob the house 1 (money = 1) and then rob house 3 (money = 3) as they are not adjacent. Total amount you can rob = 1 + 3 = 4.

Approach and Solution

Here, we are using a dynamic programming approach for this problem. We create an array dp where dp[i] will be the maximum value you can get considering the i first houses. For each i, the maximum value we can get will be either the maximum value we got from the i-1 first houses, or the maximum value we got from the i-2 first houses plus the value in the ith house. This is because we can't consider two adjacent houses, so if we rob the ith house, we have to consider the i-2 houses, not the i-1 ones.

The twist in this problem is to consider the circular adjacency. So we divide the problem into two simpler sub-problems:

• Find the maximum amount by robbing houses from the 1st to the (n-1)th and don't rob the last one.
• Find the maximum amount by robbing houses from the 2nd to the nth and don't rob the first one.

We take the maximum of the solutions of these two sub-problems.

Solution with explanation

Solution in C++

1
2cpp
3class Solution {
4 public:
5  int rob(vector<int>& nums) {
6    if (nums.empty())
7      return 0; // Handle corner case of empty input
8    if (nums.size() == 1)
9      return nums[0];  // for only one house
10    auto rob = [&](int l, int r) {
11      int prev1 = 0;  
12      int prev2 = 0;  
13      for (int i = l; i <= r; ++i) { 
14        const int dp = max(prev1, prev2 + nums[i]);
15        prev2 = prev1;
16        prev1 = dp;
17      }
18      return prev1;
19    };
20    return max(rob(0, nums.size() - 2), rob(1, nums.size() - 1));
21  }
22};
23

Python Solution

1
2python
3class Solution(object):
4    def rob(self, nums):
5        """
6        :type nums: List[int]
7        :rtype: int
8        """
9        if len(nums) == 1:
10            return nums[0]
11        return max(self.helper(nums, 0, len(nums) - 1), self.helper(nums, 1, len(nums)))
12
13    def helper(self, nums, start, end):
14        if end - start <= 1:
15            return max(nums[start:end])
16        dp = [0] * len(nums)
17        dp[start] = nums[start]
18        dp[start + 1] = max(nums[start], nums[start + 1])
19        for i in range(start + 2, end):
20            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
21        return dp[end - 1]

This Python solution follows the same logic as the previous one. Absolutely do not miss any languages!

JAVA Solution

1
2java
3public class Solution {
4    public int rob(int[] nums) {
5        if (nums == null || nums.length == 0) 
6            return 0;
7        if (nums.length == 1) 
8            return nums[0];
9        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
10    }
11
12    private int rob(int[] nums, int lo, int hi) {
13        int preRob = 0, preNotRob = 0, rob = 0, notRob = 0;
14        for (int i = lo; i <= hi; i++) {
15            rob = preNotRob + nums[i];
16            notRob = Math.max(preRob, preNotRob);
17            preNotRob = notRob;
18            preRob = rob;
19        }
20        return Math.max(rob, notRob);
21    }
22}

You can maximise your profit by either robbing at the current location and skipping the next one, or by simply moving to the next house. This is the decision you need to make at each step to maximise the loot at the end.

JavaScript Solution

1
2javascript
3var rob = function(nums) {
4    var len = nums.length
5    if(len === 0) return 0
6    if(len === 1) return nums[0]
7    if(len === 2) return Math.max(nums[0],nums[1])
8    return Math.max(robLine(nums.slice(1,len)), robLine(nums.slice(0,len-1)))
9    
10    function robLine(nums){
11        var dp = [nums[0], Math.max(nums[0], nums[1])]
12        for(let i = 2; i< nums.length; i++){
13            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
14        }
15        return dp[nums.length-1]
16    }
17};

C# Solution

1
2csharp
3public class Solution {
4    public int Rob(int[] nums) {
5        int n = nums.Length;
6        switch(n)
7        {
8            case 0: return 0;
9            case 1: return nums[0];
10            case 2: return Math.Max(nums[0],nums[1]);
11            default: return Math.Max(solve(nums, 0, n-2), solve(nums, 1, n-1));
12        }
13    }
14    
15    private int solve(int[] nums, int s, int e) {
16        int n = nums.Length;
17        int dp1 = 0;
18        int dp2 = 0;
19        
20        for(int i = s; i <= e; i++) {
21            int dp = Math.Max(dp1, dp2 + nums[i]);
22            dp2 = dp1;
23            dp1 = dp;
24        }    
25        return dp1;
26    }
27}

In all the solutions, we handle the circular adjacency by breaking the original problem into two smaller ones. Each of those sub-problems involves maximising the money robbers can get from a standard line of homes.

These solutions should work efficiently and optimally for most cases and serve as a good starting point to approach such problems.

Summary

In this problem, we applied the concept of dynamic programming to solve a house robbery problem with an additional twist. The key is to break down the problem into smaller sub-problems and solve them optimally.

By turning the circular adjacency into two different linear sub-problems, we can deal with the extra condition added to the basic house robber problem. We manage this by choosing either to rob the last house or the first one, thereby creating two separate linear arrays.

By using dynamic programming, we guarantee the optimal solution for the problem as it makes sure to check all possible combinations of houses to rob while respecting the rules connected to adjacency.

Conclusion

This problem could be helpful in teaching you the basics of dynamic programming, especially on how to divide a bigger problem into smaller problems. Also, it could serve as an example of how to make decisions that lead to an optimal solution based on the current state.

Designing a solution based on different choices available at each step is a central concept of dynamic programming, and this problem serves as a good showcase of that. Understanding how we can solve such problems will make it easier to tackle more complicated problems in the future.

I hope this article helped you understand the problem and how to approach it using different programming languages. For any questions, please let us know in the comments below.