484，打家劫舍 II

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

Sometimes it's about doing the right thing, even if it's painful inside.

有时候就是要做对的事，哪怕内心万分痛苦。

问题描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

动态规划解决

我们先来考虑这样一个问题，假如所有的房屋没有围成一个圈，也就是说第一个房屋和最后一个房屋不是挨着的，那么这道题就回退到479，递归方式解打家劫舍和477，动态规划解按摩师的最长预约时间这两道题的解了。

这里来定义一个二维数组dp[length][2]，其中length是房屋的数量。

dp[i][0]表示不偷当前房屋时能偷到的最高金额
dp[i][1]表示偷当前房屋时能偷到的最高金额

如果不偷当前房屋，那么前一家偷不偷都是可以的，我们取最大值即可

dp[i][0]=max(dp[i-1][0]，dp[i-1][1]);

如果偷当前房屋，那么前一家肯定是不能偷的，所以

dp[i][1]=dp[i-1][0]+nums[i]；

所以递推公式很容易找出来，和第477题完全一样。

边界条件是

dp[0][0]=0，第一家没偷
dp[0][1]=nums[0]，第一家偷了

代码如下

 1public int robHelper(int[] nums) {
 2    //边界条件判断
 3    if (nums == null || nums.length == 0)
 4        return 0;
 5    int length = nums.length;
 6    int[][] dp = new int[length][2];
 7    dp[0][0] = 0;//第1家没偷
 8    dp[0][1] = nums[0];//第1家偷了
 9    //从第2个开始判断
10    for (int i = 1; i < length; i++) {
11        //下面两行是递推公式
12        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
13        dp[i][1] = dp[i - 1][0] + nums[i];
14    }
15    //最后取最大值即可
16    return Math.max(dp[length - 1][0], dp[length - 1][1]);
17}

当然我们还可以进一步优化，因为上面的二维数组中每次计算当前值的时候只和前面的两个值有关，其他的都不会在用到了，所以这里可以使用两个变量即可，不需要申请一个二维数组。

1private int robHelper(int[] num) {
2    int steal = 0, noSteal = 0;
3    for (int j = 0; j < num.length; j++) {
4        int temp = steal;
5        steal = noSteal + num[j];
6        noSteal = Math.max(noSteal, temp);
7    }
8    return Math.max(steal, noSteal);
9}

到这里还没完，上面我们假设所有的房屋没有构成一个环，但这道题中所以的房屋是围成一个环形的。

如果偷第1家，就不能偷最后一家，所以可偷的范围是[0，length-2]。
如果不偷第1家，那么就可以偷最后一家，可偷的范围是[1，length-1]。

所以最终代码如下

 1public int rob(int[] nums) {
 2    if (nums.length == 1)
 3        return nums[0];
 4    //可以偷第一家，但不能偷最后一家
 5    int robFirst = robHelper(nums, 0, nums.length - 2);
 6    //可以偷最后一家，但不能偷第一家
 7    int robLast = robHelper(nums, 1, nums.length - 1);
 8    //选择偷第1家和不偷第1家结果的最大值
 9    return Math.max(robFirst, robLast);
10}
11
12private int robHelper(int[] num, int start, int end) {
13    int steal = 0, noSteal = 0;
14    for (int j = start; j <= end; j++) {
15        int temp = steal;
16        steal = noSteal + num[j];
17        noSteal = Math.max(noSteal, temp);
18    }
19    return Math.max(steal, noSteal);
20}