打家劫舍II

力扣 213. 打家劫舍 II

题目说明

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

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

提示：
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000

示例

例1

1
2
3

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

例2

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

例3

1 2	输入：nums = [0] 输出：0

笔者理解

此题是一道动态规划算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题很适用于动态规划，此题与198. 打家劫舍不同的是规定了首尾两栋房子不能同时偷，我们只要分成两种情况来分开讨论就好了，让我们来看看具体如何实现的吧。

实现

public int rob(int[] nums) {
        int n = nums.length;

        if (n == 1) {
            return nums[0];
        }
        
        // 根据题目约束，我们有两种选择，一种是选择偷盗第一间屋子而不偷最后一间屋子的最优收获，
        // 另一种是选择偷盗最后一间屋子而不偷第一间屋子的最优收获
        int restFirst = 0;
        int stealFirst = nums[0];

        int restLast = 0;
        int stealLast = nums[1];

        int temp = 0;

        for (int i = 1; i < n; i++) {
            
            if (i < n - 1) {
                // 用以暂存上一个房子不偷的值
                temp = restFirst;
                // 当前房子不偷的最优选择是上一个房子偷与上一个房子不偷的最优者
                restFirst = Math.max(restFirst, stealFirst);
                // 当前房子不偷的最优选择是上一个房子偷与上一个房子不偷，当前房子偷的最优者
                stealFirst = Math.max(stealFirst, temp + nums[i]);
            }
            
            if (i > 1) {
                temp = restLast;
                restLast = Math.max(restLast, stealLast);
                stealLast = Math.max(stealLast, temp + nums[i]);
            }
            
        }

        return Math.max(Math.max(stealFirst, restFirst),Math.max(stealLast, restLast));
    }