LeetCode213. 打家劫舍 II

题目：

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

分析

和之前的打家劫舍几乎差不多，之前的屋子是一条链，而现在的屋子是一个圈儿，我就把它分成了两种分别计算，第一种是：第一个房子到倒数第二个房子， 第二种是：第二个房子到最后一个房子，分别去计算它们的最大偷窃数，取最大的返回。

一组链式房子的最大窃取数的方法： 根据前面的最大窃取量，来决定当前最大窃取量。比如 一组数： 7 3 5 6 9 2

当位置在第一个房子时， 最大窃取量为 7；

当位置在第二个房子时，最大窃取量为 7 ；因为两个房子不能连续偷，而且偷第一个房子比偷第二个房子偷的多

当位置在第三个房子时，最大窃取量为 7 + 5 = 12；对比前一位房子最大偷窃数量为 7 ，显然这个房子里的东西要偷

当位置在第四个房子时，最大窃取量为 6 + 7 = 13；对比前一位房子最大偷窃数量为 12 ，显然这个房子里的东西要偷

当位置在第五个房子时，最大窃取量为 9 + 12 = 21；对比前一位房子最大偷窃数量为 13 ，显然这个房子里的东西要偷

当位置在第六个房子时，最大窃取量为 21；对比前一位房子最大偷窃数量为 21 ，显然偷了这个房子里的东西偷到的数量13+2=15 不合算嘛 偷了它偷到的总量就少了嘛

所以最后最大偷窃数位 21。

代码

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0 ) return 0;
        if (len == 1) return nums[0];
        if (len == 2) return Math.max(nums[0],nums[1]);

        int[] nums1 = new int[len-1];
        int[] nums2 = new int[len-1];
        for (int i = 0; i < len-1; i++) nums1[i] = nums[i];
        for (int i = 1; i < len; i++)  nums2[i-1] = nums[i];

        return Math.max(robSingle(nums1),robSingle(nums2));
    }
    
    public static int robSingle(int[] nums){
        int len = nums.length;
        int[] arrays = new int[len];
        for (int i = 0; i < len; i++) {
            if (i == 0) arrays[i] = nums[i];
            else if (i == 1) arrays[i] = Math.max(nums[i],nums[0]);
            else arrays[i] = Math.max(arrays[i-1],arrays[i-2]+nums[i]);
        }

        return arrays[len-1];

    }

}