力扣213——打家劫舍 II

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

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

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

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

        // 因为收尾相连，无法按照最初的动态规划来做，因为没有一个可以开始的点。
        // 那么就将未知问题转化为已知问题，针对首尾两个节点，可以有三种情况：
        // 1、首尾节点都不选择
        // 2、只选择首节点，不选择尾结点
        // 3、只选择尾结点，不选择首节点
        // 因为是要取最大值，且是非负整数数据，所以只考虑后两种情况

        return Math.max(
            // 只选择首节点，不选择尾结点
            calMax(nums, 0, nums.length - 2),
            // 只选择尾结点，不选择首节点
            calMax(nums, 1, nums.length - 1)
        );
    }

    public int calMax(int[] nums, int start, int end) {
        // 存储当前位置，下一个位置，和再下一个位置的结果
        int current = 0;
        int next_1 = 0;
        int next_2 = 0;
        // 动态规划，利用中间结果，寻找最大值
        for (int i = end; i >= start; i--) {
            current = Math.max(
                // 当前不偷
                next_1,
                // 当前偷
                nums[i] + next_2
            );
            next_2 = next_1;
            next_1 = current;
        }
        return current;
    }
}