213. House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution:

This problem is in addition to the original problem: House Robber.

The only difference here is the cycle. If we can break the cycle, we should be able to reuse the code in previous problem. 

It is still state machine problem, in final result, each house may only have two states, either it is robbed or not. We can break the cycle by calculating both states of a single house. We can break the cycle in any of the houses, for simplicity, I choose the first one, nums[0], if house 0 is not robbed, there are no restrictions that if we rob house[1] and house[n-1], so the maximum money we can rob is esentially the same as House Robber from 1 to n-1 If we rob house[0], the maximum money we can rob will be money[0] + house robber from 2 to n-2, because house[1] and house[n-1] are adjacent to house[0] so we can't rob them. In this way, we successfully broke the cycle and reused the same idea of house Robber.

  public int rob(int[] nums) {  
     if(nums==null || nums.length==0) return 0;  
    return Math.max(helper(nums,1,nums.length-1), nums[0]+helper(nums,2,nums.length-2));  
   }  
   public int helper(int[] nums, int start, int end){  
     if(start>end) return 0;  
     int robbed=0;  
     int unRobbed=0;  
     for(int i=start;i<=end;i++){  
       int temp=unRobbed;  
       unRobbed=Math.max(robbed,unRobbed);  
       robbed=nums[i]+temp;  
     }  
     return Math.max(robbed,unRobbed);  
   }