问题描述：
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
Example
示例 1：
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
题目链接：213. 打家劫舍 II (难度:中等)
思路
对于首尾的情况，一共可以分为4种
- 首尾都不偷；
- 偷首不偷尾；
- 偷尾不偷首；
- 首尾都偷；
显然由题目的描述可知，第 4 种情况会触发报警系统。因此我们需要排除第 4 种情况。另外，第 1 种情况，其实已经包含在第 2 种和第 3 种情况当中。因此我们只需要考虑第 2 种和第 3 种情况即可，可以采用两次dp，一次从0偷到n-1，一次从1偷到n，返回两次dp中的最大值即可。
动态规划三要素
- dp定义：
dp[i] = x：从第 i 间房开始偷，小偷所能得到的最大金额- 状态与状态转移方程：
①、第 i 间房不偷，则去第 i + 1 间房看看，dp[i] = dp[i+1]
②、第 i 间房偷，则去第 i + 2 间房看看，dp[i] = dp[i + 2] + nums[i];
方程：dp[i] = max(dp[i + 1], dp[i + 2] + nums[i]);- 初态与终态
初态：dp[n] = 0
终态：dp1[0], dp2[1]
其中，dp1[i]表示从0偷到n-1号房，dp2[i]表示从1偷到n号房
代码
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty()) return 0;
int n = nums.size();
if(n == 1) return nums[0];
// 此处采用递推实现，dp1_i_1 表示 dp1[i-1]，dp1_i_2 表示 dp1[i-2]，以此类推
int dp1_i = 0, dp1_i_1 = 0, dp1_i_2 = 0;
int dp2_i = 0, dp2_i_1 = 0, dp2_i_2 = 0;
for(int i = n - 1; i >= 1; --i){
dp1_i = max(dp1_i_1, dp1_i_2 + nums[i]);
dp1_i_2 = dp1_i_1;
dp1_i_1 = dp1_i;
}
for(int j = n - 2;j >= 0;--j){
dp2_i = max(dp2_i_1,dp2_i_2 + nums[j]);
dp2_i_2 = dp2_i_1;
dp2_i_1 = dp2_i;
}
return dp1_i > dp2_i ? dp1_i : dp2_i;
}
};
执行结果： 0 ms, 7.9 MB
