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.

解析：

因为第一个元素和最后一个元素不能同时选择，可以将最后一个元素去掉求前面的满足条件元素的和，同理可将第一个元素去掉求后面的满足条件元素的和。

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

213. House Robber II

原文：http://www.cnblogs.com/ghuosaao/p/6483246.html