House Robber II 534

Question

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.

Example

nums = [3,6,4], return 6

Solution

这道题和I的思路一样，但是因为有环，所以不能同时抢第一家和最后一家。因此，只要把第一家或者最后一家去掉，再用I的方法求剩下的最大值，最后再在两种情况里面取大的那个即可。

代码如下：

public class Solution {
    /**
     * @param nums: An array of non-negative integers.
     * return: The maximum amount of money you can rob tonight
     */
    public int houseRobber2(int[] nums) {
        // write your code here
        if(nums == null || nums.length == 0){
            return 0;
        }

        int n = nums.length;
        if(n == 1){
            return nums[0];
        }

        int[] num1 = new int[n - 1];
        int[] num2 = new int[n - 1];
        for(int i = 0; i < n - 1; i++){
            num1[i] = nums[i];
            num2[i] = nums[i + 1];
        }

        return Math.max(houseRobber1(num1), houseRobber1(num2));
    }

    private int houseRobber1(int[] nums){
        if(nums == null || nums.length == 0){
            return 0;
        }

        int n = nums.length;
        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = nums[0];

        for(int i = 2; i <= n; i++){
            dp[i % 2] = Math.max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[i - 1]);
        }

        return dp[n % 2];
    }
}