House Robber I, II, III

House Robber can be found on leetcode, there are three variants to the problem House Robber I , House Robber II , House Robber III

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

House Robber I

If the money stashed in n houses in the street is represented by array of integers A[1],A[2]...A[n], where A[i] is positive integer.

If we have [5,4,6,4,2,9] as the array, below diagram represents all possible ways to rob houses.

For house located at index i, lets assume moneyStashed[i] is the money stashed,

• if the robber has already robbed i-1 house he can’t hence the total money stashed at i will be the money stashed at i-1 in this case = moneyStashed[i-1]
• if the robber didn’t rob i-1 house, then he can rob ith house, so the money he stash will be what he stashed before i-1 house and the money he will stash from ith house = A[i] + moneyStashed[i-2]

Since we need to help the robber maximize his profit, we come up with the relation moneyStashed[i] = MAX(moneyStashed[i-1],moneyStashed[i-2]+A[i])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==1)return nums[0];
        
        int dp[] = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],nums[0]);
        
        for(int i=2;i<n;i++){
            dp[i] = Math.max(dp[i-1],nums[i]+dp[i-2]);
        }
        
        return dp[n-1];   
    }
}

We can also optimize space in above problem, as the value dp[i] only depends on previous two values dp[i-1] & dp[i-2]

House Robber II

In this problem the houses are now arranged in a circle, that is the last house is adjacent to first house.

When houses are in a circle, the 1st house and last house will become adjacent houses, that would mean we can only rob one of them at a time.

• We can keep first house and exclude last house, and rob houses normally as we would do when houses are arranged linearly.
• We can keep last house and exclude first house, and rob houses normally as we would do when houses are arranged linearly.

Our solution will be max amongst them, which can help the robber rob max money. In following code rob(nums,i,j), returns money stashed when robber has only i to j houses(both inclusive) to rob arranged in a line. Hence maxMoney = MAX (rob(nums,0,nums.length-2), rob(nums,1,nums.length-1))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    public int rob(int[] nums) {
        
        if(nums.length==1){
            return nums[0];
        }
        
       return Math.max(rob(nums,0,nums.length-2),rob(nums,1,nums.length-1));
   }
    
    public int rob(int[] nums, int i, int j){
        
        int prev = 0;
        int prev_prev = 0;
        
         for(int k=i;k<=j;k++){
             int temp = prev;
             prev = Math.max(prev_prev+nums[k],prev);
             prev_prev = temp;
         } 
        
        return Math.max(prev,prev_prev);
    }

House Robber III

In this problem, the houses are arranged in a binary tree, the robber can only start from root and can’t rob houses that are directly connected.

The money stashed is represented by the node value of the tree. The robber starts from root, and has to choose houses which are not directly connected to rob maximum money.

For the above example, the best way robber can rob to get maximum profit is represented in the image.

At any node we will have two option:

• take current node and process its grandchild nodes as it will be the next non-connected node to it, Or
• don’t take current node and process its child nodes

We will have overlapping subproblems here, When robber robs current node the child, grandchild would also be processed, when child is processed, the grandchild will get processed again. We can store those results in a map so we don’t need to re-process them.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    public int rob(TreeNode root) {
        if(root==null)return 0;
        return  rob(root,new HashMap<>());
        
    }

    int rob(TreeNode node, Map<TreeNode,Integer> map){
        
        if(node==null)return 0;
        if(map.get(node)!=null)return map.get(node);
        int sol = node.val;
        
        if(node.left!=null){
            sol+=rob(node.left.left,map)+rob(node.left.right,map);
        }
        
        if(node.right!=null){
            sol+=rob(node.right.left,map)+rob(node.right.right,map);
        }
        
        map.put(node,
                Math.max(sol, rob(node.left,map)+rob(node.right,map)));
        return map.get(node);
    }