Labels

Saturday, July 25, 2015

House Robber II

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.

Refer from House Robber I
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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
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.

My Thinkings:

The only difference is it's a circle now instead of a straight line. The last one cant be robbed if the first one has been robbed. If I am going to use the same Dynamic Programming Process, maintaining an array to store current optimized robbery status, I can tell if the first house has been robbed or not from if(opt[1] == 0). However, I cant control the robber not to rob house 1 since opt[1] will always equal to the value in the first house.

That seems to stop me from considering it a DP process. Then I came up with a more mathematics thought-- each time spin the house value by one step, calling DP solution on each new array. Now, I realize how stupid I am. In this way, I still didn't solve the circling thing-- how to include both cases, with the first robbed and with the first one save. And since every house is in a circle, it really doesn't matter where is the starting point if your algorithm is a correct one.

Then I turned to DFS. Since a lot of DP problem can be rewrote in a cached DFS(memorized DFS). It took me some time and finally I gave up this idea since I dont know what to cache.

The final result is easy. It is always like that. I realize I just need to change the initial condition and  run DP twice.

 public class Solution {  
   public int rob(int[] nums) {  
     return Math.max(circle_rob(nums, true), circle_rob(nums, false));  
   }  
     
   private int circle_rob(int[] nums, boolean robFirst){  
     // edge case  
     if(nums == null || nums.length == 0) return 0;  
       
     int[] opt = new int[nums.length+1];  
       
     // initial condition  
     opt[0] = 0;  
     opt[1] = robFirst?nums[0]:0;  
       
     // iteration  
     for(int i = 2;i < opt.length;i++){  
       if(i!=opt.length-1){   
         // normal case  
         opt[i] = Math.max(opt[i-2] + nums[i-1], opt[i-1]);  
       }else{  
         // last robbery  
         opt[i] = robFirst?opt[i-1]:Math.max(opt[i-2]+nums[i-1],opt[i-1]);  
       }  
     }  
       
     return opt[opt.length-1];  
   
   }  
     
     
 }  

1 comment:

  1. My python Solution:
    class Solution(object):
    def rob(self, nums):
    “””
    :type nums: List[int]
    :rtype: int
    “””
    n = len(nums)
    if n == 0: return 0
    if n < 4: return max(nums)

    first, second = 0, 0
    for i in nums[:-1]: first, second = second, max(first + i, second)
    result = second

    first, second = 0, 0
    for i in nums[1:]: first, second = second, max(first + i, second)
    return max(result, second)

    URL: http://traceformula.blogspot.com/2015/08/house-robber-ii.html

    ReplyDelete