问题
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 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思路：动态规划
我们之前在解决“打家劫舍”问题时，是没有考虑到第一间房屋和最后一间房屋连通的情况的。根据动态规划思想，我们得到如下的状态转移方程
其中$dp[i]$表示在$nums[0:i]$中可以偷取到的最大金额。
而如今，需要特别考虑首尾相连的问题。我们仍然记房屋存放金额数组为$nums[]$，其长度为$n$，那么也就是说
- 如果选择偷取最后一间房屋，那么就不可以偷取第一间房屋，则考虑的偷取范围为$[1,n-1]$
- 如果选择不偷取最后一间房屋，那么便可以偷取第一间房屋，则考虑的偷取范围为$[0,n-2]$
因此，针对上面的两种情况，我们其实可以分别按照“打家劫舍”中的解题思路算法运行一遍，然后取最大值即为最后的答案了。
代码
class Solution {
public:
int DP(vector<int>& nums, int start, int end) {
// [start, end]
if(start == end) return nums[start];
int dp[105];
memset(dp, 0, sizeof(dp));
int i;
dp[start] = nums[start], dp[start+1] = max(nums[start], nums[start+1]);
int ans = max(dp[start], dp[start+1]);
for(i=start+2; i<=end; i++) {
dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
ans = max(ans, dp[i]);
}
return ans;
}
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
int ans1 = DP(nums, 1, n-1);
int ans2 = DP(nums, 0, n-2);
return max(ans1, ans2);
}
};
