☆打卡算法☆LeetCode 213. 打家劫舍 II 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个代表每个房屋存放金额的整数数组，计算再不触发警报装置的情况下能够窃取的最高金额。”

题目链接：

来源：力扣（LeetCode）

链接： 213. 打家劫舍 II - 力扣（LeetCode）

2、题目描述

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

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

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

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

二、解题

1、思路分析

这道题是198题打家劫舍的进阶版本，和198题不同的是这道题中的房屋是首尾相连的。

第一间房屋和最后一间房屋相邻，因此第一间房屋和最后一间房屋不能同一晚上偷窃。

这道题和198题相似，也可以使用动态规划来解决。

首先，定义动态规划的列表dp，dp[i]表示前i个房子在满足条件下的偷窃最高金额，此房间的简直为num。

因为不能抢相邻的房子，意味着抢n+1间就不能抢第n间，那么前n+1间能偷窃的最高金额dp[n+1]有两种情况，在这两种情况中去较大值：

• 不抢第n+1房间，因此第n个房子的最高金额为dp[n+1]=dp[n]
• 抢第n+1房间，不抢第n房间，因此最高金额为dp[n+1]=dp[n-1]+num

假设第n间被偷，那么此时dp[n+1]=dp[n]+num不可取，因为偷了第n间就不能偷第n+1间。

那么最终的转移方程就是：dp[n+1]=max(dp[n],dp[n-1]+num)。

返回dp列表最后一个元素值，就是所有房间最大偷窃价值。

2、代码实现

代码参考：

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

    public int robRange(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

image.png

3、时间复杂度

时间复杂度：O(n)

其中n是数组的长度，需要对数组遍历两次。

空间复杂度：O(1)

只需要常数级的变量空间。

三、总结

环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，

因此可以把此环状排列房间问题约化为两个单排排列房间子问题(198)：

在不偷窃第一个房子的情况下（即 nums[1:]），最大金额是p1；

在不偷窃最后一个房子的情况下（即 nums[:n-1]），最大金额是p2。

综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1,p2)。