每日一题_动态规划_213_环形房屋抢劫

最近由于电脑出现问题，更换了风扇，导致学习进度受到了一些影响。不过，明天一定会加倍努力学习。另外，今天没能按时与师妹见面，非常抱歉。

日期: 2021/10/29
题目链接: 213. 环形房屋抢劫（LeetCode）
汇总题目: 每日一题系列_算法提升

在一个环形排列的房屋中，每个房屋内都藏有一定的现金。但是，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算在不触动警报的情况下，能够偷窃到的最高金额。

这个问题的关键在于房屋是环形排列的，因此第一家和最后一家不能同时被偷。我们可以将问题分解为两个子问题：
1. 假设偷了第一家，那么最后一家就不能偷，考虑的范围是 [0, n - 2]。
2. 假设没有偷第一家，那么最后一家就可以考虑偷，考虑的范围是 [1, n - 1]。
最后取这两个子问题的最大值即可。

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;if (n == 1) return nums[0];if (n == 2) return max(nums[0], nums[1]);return max(rob_range(nums, 0, n - 2), rob_range(nums, 1, n - 1));}int rob_range(vector<int>& nums, int start, int end) {vector<int> dp(end - start + 1);dp[0] = nums[start];dp[1] = max(dp[0], nums[start + 1]);for (int i = 2; i < end - start + 1; i++) {dp[i] = max(dp[i - 2] + nums[start + i], dp[i - 1]);}return dp[end - start];}
};