LeetCode -- House Robber II

LeetCode -- 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.


與之前的第一個版本類似，只是這次的數組首尾的馬會被看成是相鄰的，即不能同時搶第1匹和最後1匹。


思路：
本題依然使用DP來解，只是需要基於第1種解法考慮兩種特殊情況即可（搶第1匹放棄最後一匹和放棄第1匹搶最後1匹）：
1. 對第[0,n-1]匹馬執行DP ， 得到max1
2. 對第[1,n]匹馬執行DP，得到max2


最後返回max1與max2的最大值。


注意，由於是環，因此小於4匹馬時，只需要返回數組最大值即可。




實現代碼：

public int Rob(int[] nums) 
    {
        if(nums == null || nums.Length == 0)
    	{
    		return 0;
    	}
    	
    	if(nums.Length < 4){
    		return nums.Max();
    	}
    	
    	var list = new List(nums);
    	var first = list[0];
    	list.RemoveAt(0);
    	var max1 = Max(list);
    	
    	list.Insert(0 , first);
    	list.RemoveAt(list.Count-1);
    	var max2 = Max(list);
    	
    	return Math.Max(max1 , max2);
    }




    private int Max(IList nums)
    {
    	var len = nums.Count;
    	var dp = new int[len + 1];
    	dp[0] = 0;
    	dp[1] = Math.Max(nums[0], 0);
    	
    	for(var i = 2;i < len + 1; i++){
    		dp[i] = Math.Max(dp[i-1], dp[i-2] + nums[i-1]);
    	}
    
    	return dp[len];
    }