1. 题目解析
题目链接：213. 打家劫舍 II
这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。
2.算法原理
这个问题是经典的“打家劫舍”问题的变种，原问题是在单排房屋中进行偷窃，而这个问题则是在环形排列的房屋中进行。环形排列的特点在于首尾相连，这为我们设计算法带来了新的挑战。然而，通过一些巧妙的转换，我们可以将这个问题分解为两个单排问题来解决。
首先，我们需要明确环形排列带来的限制：由于首尾相连，我们不能同时偷取第一个和最后一个房屋，因为这会导致连续的偷窃行为被发现。因此，我们可以将问题拆分为两种情况来考虑：
-
偷取第一个房屋时的最大金额（设为x）：在这种情况下，我们不能偷取最后一个房屋，因为这将构成一个闭环。因此，我们的搜索范围变成了从第一个房屋到倒数第二个房屋，即区间[0, n-2]。
-
不偷取第一个房屋时的最大金额（设为y）：在这种情况下，我们可以偷取最后一个房屋，因为第一个房屋已经被排除在外，不会构成闭环。因此，我们的搜索范围变成了从第二个房屋到最后一个房屋，即区间[1, n-1]。
通过分别计算这两种情况下的最大金额，我们可以得到两个结果：x和y。最终，我们只需要取这两个结果中的较大值，即为在环形排列的房屋中进行偷窃能够获得的最大金额。
3.代码编写
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
}
int rob1(vector<int>& nums, int left, int right) {
if(left > right) return 0;
int n = nums.size();
vector<int> f(n), g(n);
f[left] = nums[left]; // 初始化
for (int i = left + 1; i <= right; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[right], g[right]);
}
};The Last
嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。
觉得有点收获的话，不妨给我点个赞吧！
如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~