打家劫舍II213
题干
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 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
思路
成环的DP，该怎么解？我们将引申出多种情况。
首先是这个数组成环之后，我们首先要考虑的就是首尾元素。
- 考虑不包含首尾元素
- 考虑只包含首元素
- 考虑只包含尾元素
这三种情况考虑完毕，那么第一种情况是可以忽略的，因为第二、第三种情况是已经把第一种情况包含在内了。
所以我们可以复用打家劫舍的代码，用两次比较最大值。
题解
class Solution {
public:
// 主函数：解决环形街区打家劫舍问题
int rob(vector<int>& nums) {
// 如果只有一间房屋，直接返回其金额
if(nums.size() == 1) return nums[0];
// 如果有两间房屋，选择金额较大的那间（因为不能同时偷相邻的，且环形相邻指首尾也算相邻）
if(nums.size() == 2) return max(nums[0], nums[1]);
// 情况1：不偷最后一间房屋，即考虑下标 [0, n-2] 的线性街区
int result_1 = robSingle(nums, 0, nums.size() - 2);
// 情况2：不偷第一间房屋，即考虑下标 [1, n-1] 的线性街区
int result_2 = robSingle(nums, 1, nums.size() - 1);
// 返回两种情况中的最大值
return max(result_1, result_2);
}
// 辅助函数：处理线性街区（非环形）的打家劫舍问题
// 参数：nums 原数组，start_index 起始下标，end_index 结束下标（闭区间）
int robSingle(vector<int>& nums, int start_index, int end_index) {
// 计算当前考虑的子数组长度
int len = end_index - start_index + 1;
// dp[i] 表示在子数组前 i+1 个元素（即下标从 start_index 到 start_index+i）中能偷到的最大金额
// 这里直接分配 len 大小的 dp 数组
vector<int> dp(len, 0);
// 初始化前两个 dp 值（对应子数组的第一个和第二个元素）
dp[0] = nums[start_index]; // 只有一间房屋时，直接偷
dp[1] = max(nums[start_index], nums[start_index + 1]); // 两间房屋时，偷金额较大的
// 从第三间房屋开始递推（下标 i 对应子数组中的第 i+1 个元素）
for(int i = 2; i < len; ++i) {
// 当前房屋在 nums 中的实际下标 = start_index + i
// 状态转移方程：要么不偷当前房屋（金额 = dp[i-1]），
// 要么偷当前房屋（金额 = dp[i-2] + nums[当前实际下标]）
dp[i] = max(dp[i-1], dp[i-2] + nums[i + start_index]);
}
// 返回子数组中最后一家对应的 dp 值，即最大偷窃金额
return dp[len - 1];
}
};