[数据结构与算法]每日一道算法题(7) -- 打家劫舍II

题目

LeetCode :213?

思路分析

跟打家劫舍的思路一样，只是加了点附件条件，就头取尾不取，尾取头不取，所以我们要将其分为两个范围：头到尾- 1和头- 1到尾，取其中的最大值。

?

代码展示

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1)
            return nums[0];
        return Math.max(maxCost(nums, 0, nums.length - 2), maxCost(nums, 1, nums.length - 1));
    }
    public int maxCost(int[] nums, int start, int end){
        int one, second;
        one = second = 0;//初始化，将尾部的 + 1， + 2初始化为0,因为此两处已经没房子了
        for(int i = end; i >= start; i--){
            int temp = Math.max(one, second + nums[i]);
            second = one;
            one = temp;
        }//从后向前推
        return one;
    }
}