leetCode 213. 打家劫舍 II 动态规划 房间连成环怎么偷呢？

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

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

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

示例 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

>>思路和分析

与leetCode 198.打家劫舍 动态规划是差不多的，唯一区别就是成环了。

对于一个数组，成环的话主要有如下几种情况：

• 情况一，考虑不包含首尾元素

• 情况二，考虑包含首元素，不包含尾元素

• 情况三，考虑包含尾元素，不包含首元素

如果是线性数组的话，就是leetCode 198.打家劫舍 动态规划 。一旦连成环了，就开始犯懵了(=@__@=)，不知道起点应该在哪里，终点应该在哪里。那么起点和终点我到底选不选呢？就会陷入这个泥潭里~

那么连成环的房间我们该从哪里思考呢？

在连成环的线性数组中，首元素和尾元素是相邻的。那么如果首元素和尾元素只能选一个，要不就选首元素要不就选尾元素，要不就是首尾元素都不选。此时可以化为3种情况。

• 情况一，首尾都不考虑了，此时连成环对线性数组没有影响了。只考虑中间那段，此时就是一个线性数组，可以用线性数组的方式来解决它。可用leetCode 198.打家劫舍 的处理方式一样了
• 情况二，考虑首元素，但不考虑尾元素。所以即使你的首尾元素相邻在一起对此无影响，此时就是一个线性数组，可以用线性数组的方式来解决它。可用leetCode 198.打家劫舍 的处理方式一样了。
• 情况三，考虑尾元素，但不考虑首元素。所以即使你的首尾元素相邻在一起对此无影响，此时就是一个线性数组，可以用线性数组的方式来解决它。可用leetCode 198.打家劫舍 的处理方式一样了。

仔细分析情况二和情况三，是包含了情况一的。情况二是连首元素和中间部分都考虑了，那中间部分所得到的最优值，那么情况二也包含了。有友友可能就疑惑了(O_O)? 你情况二选头元素了呀，怎么能包含我情况一呢？这么想其实就是陷入了误区，因为这里是考虑的范围，是把首元素考虑进去了，没说一定要选首元素。选不选它，是由我们递推公式去决定的。这里考虑的范围，仅仅是遍历的范围，即遍历递推公式的范围。通俗讲就是这个范围就这么大，那么选不选首元素，是递推公式来决定的，没说一定要选首元素。所以说在这个范围内，考虑最优解是一定包含了情况一范围内的最优解。情况三也同理，它的范围内的最优解也一定包含了情况一范围内的最优解。

“考虑”二字，就很绝！例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！对于情况三，取nums[1] 和 nums[3] 就是最大的！！！而情况二 和 情况三 都包含了情况一了，所以只会考虑情况二 和 情况三 就可以了。

这是 leetCode 198.打家劫舍 动态规划 的核心代码

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i=2;i < nums.size();i++) {
            dp[i] = max(dp[i-1],dp[i-2] + nums[i]);
        }
        return dp[nums.size()-1];
    }
};
 
// 时间复杂度: O(n)
// 空间复杂度: O(n)

我们把它抽离出来，就是robRange这个函数，我们可以传入nums,start,end这三个参数，可以实现截取数组的操作，以此实现情况二和情况三，然后将其各自得到的返回值中取一个最大值。这样就可以把这个环形问题化解为一个线性数组的问题。思路清晰~

// 注意注释中的情况二情况三，以及把198.打家劫舍的代码抽离出来了
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2); // 情况二
        int result2 = robRange(nums, 1, nums.size() - 1); // 情况三
        return max(result1, result2);
    }
    // 198.打家劫舍的逻辑
    int robRange(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

#总结

成环之后，厘清“考虑房间” 和 “偷房间”概念，然后厘清情况一、情况二、情况三的“考虑”范围，具体房间偷与不偷则交给递推公式去选择。

考虑环形问题的时候，其实有的时候环形问题不利于我们的思考，会纠结起始位置在哪里，终止位置在哪里，选起始位置呢还是选末尾位置呢？那其实可以适当将这个环形给它展开，展开成一个线性的结构，接着单独再去考虑首元素和尾元素选还是不选，从而列举出三种情况。针对这三种情况再分析，情况二 和 情况 三 是包含了情况一的，那接下来就是一个线性数组问题了，和leetCode 198.打家劫舍 的处理方式一样了。

参考和推荐文章、视频

动态规划，房间连成环了那还偷不偷呢？| LeetCode：213.打家劫舍II_哔哩哔哩_bilibili

代码随想录 (programmercarl.com)

我的往期文章 

leetCode 198.打家劫舍 动态规划_呵呵哒(￣▽￣)"的博客-CSDN博客