05、打家劫舍II

厨子大约 4 分钟数据结构算法算法基地面试动态规划刷题程序厨校招社招

完成了打家劫舍 1，我们继续来看打家劫舍 2,不过这个题目，如果没做过的话，确实不容易想到解法，大家可以先试着想一下，10 min 没思路的话，直接看题解就好啦

https://leetcode.cn/problems/house-robber-ii/open in new window

题目描述

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

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

示例 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 = [1,2,3]
输出：3

约束条件:

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

很明显，题目的难度升级了！！！变成环了，第一个和最后一个屋子也有了邻居

环形数组的特殊性

问题对比

LeetCode 198. 打家劫舍（线性）:
房屋: [2, 7, 9, 3, 1]
      0  1  2  3  4
不能偷相邻的即可


LeetCode 213. 打家劫舍 II（环形）:
房屋: [2, 7, 9, 3, 1]
      0  1  2  3  4
      ↑          ↑
      └──环形──┘

特殊约束：0 和 4 也是相邻的！

环形约束分析

环形意味着：
第一个房屋 (0) 和最后一个房屋 (n-1) 相邻

如果偷第一个房屋，就不能偷最后一个
如果偷最后一个房屋，就不能偷第一个

解决方案：
分两种情况计算，取最大值
1. 考虑房屋 [0, n-2]，不包括最后一个
2. 考虑房屋 [1, n-1]，不包括第一个
我们只需要将上述两次情况分别求解，最后选择最大的那个就好了呀！将环形问题转化为两个线性问题

图解示例

nums = [2, 3, 2]

环形结构：
    2
   / \
  3 — 2
   

情况1：考虑 [2, 3]（不包括最后一个）
  可以偷：2 或 3
  最大：3

情况2：考虑 [3, 2]（不包括第一个）
  可以偷：3 或 2
  最大：3

答案：max(3, 3) = 3 ✓

动态规划解法⭐

核心思想

将环形问题转化为两个线性问题：

偷 [0, n-2]，即不考虑最后一个房屋
偷 [1, n-1]，即不考虑第一个房屋

对这两种情况分别应用打家劫舍 I 的算法，取最大值。

代码实现

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        // 边界情况
        if (n == 0) {
           return 0;
        }
     
        if (n == 1) {
           return nums[0];
        }

        // 情况1：偷 [0, n-2]，不考虑最后一个房屋
        int max1 = robRange(nums, 0, n - 2);

        // 情况2：偷 [1, n-1]，不考虑第一个房屋
        int max2 = robRange(nums, 1, n - 1);

        // 返回两种情况的最大值
        return max(max1, max2);
    }

private:
    // 打家劫舍 I 的解法（线性数组）
    int robRange(vector<int>& nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int prev2 = nums[start];
        int prev1 = max(nums[start], nums[start + 1]);

        for (int i = start + 2; i <= end; i++) {
            int curr = max(prev1, nums[i] + prev2);
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
};