213. 打家劫舍 II

代码

class Solution {
    /**
    分三种情况
    1：头尾均不选
    2: 考虑含头不含尾的情况
    3：考虑含尾不含头的情况（2,3包括1）
    */
    public int rob(int[] nums) {
        int size = nums.length;
        if( size < 2 ) {
            return nums[0];
        }
        return Math.max( robMax(Arrays.copyOfRange(nums,0,size - 1)) , robMax(Arrays.copyOfRange(nums,1,size) ) );
    }
    public int robMax(int[] nums ) {
        int size = nums.length;
        if(size < 2) return nums[0];
        int [] dp = new int [size];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2; i < size; i++ ) {
            dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);
        }
        return dp[size - 1];
    }
}