前言：上一个题目所求的数组是线性的，首尾并不影响结果。这道题目的数组的首尾相连接，构成一个环。再来求这一道题目，难度进一步上身。我们直接进入题目：
一.题目
二.在上一道题目的基础上进行剖析
对于一个数组，成环的话主要有如下三种情况：
- 情况一：考虑不包含首尾元素
- 情况二：考虑包含首元素，不包含尾元素
- 情况三：考虑包含尾元素，不包含首元素
注意我这里用的是"考虑"，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！ 对于情况三，取nums[1] 和 nums[3]就是最大的。
而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。
分析到这里，本题其实比较简单了。 剩下就和上一道题目就是一样的了。
代码如下：
// 注意注释中的情况二情况三，以及把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]; } };
成环之后还是难了一些的， 不少题解没有把“考虑房间”和“偷房间”说清楚。
这就导致大家会有这样的困惑：情况三怎么就包含了情况一了呢？ 本文图中最后一间房不能偷啊，偷了一定不是最优结果。
Java代码如下：
class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; int len = nums.length; if (len == 1) return nums[0]; return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len)); } int robAction(int[] nums, int start, int end) { int x = 0, y = 0, z = 0; for (int i = start; i < end; i++) { y = z; z = Math.max(y, x + nums[i]); x = y; } return z; } }
