题目来源
本题来源为：
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
题目解析
这道题是在打家劫舍I的基础上加上了首尾相连的不能盗窃。
算法原理
在写状态表示之前，先预处理一下：
分两种情况，在1位置时选不选择盗窃；
要是选择在0位置不盗窃：
就转化成了在1~n-1区间内进行一次打家劫舍I问题。
要是选择在0位置盗窃：
就转化成了在2~n-2区间内进行一次打家劫舍I问题。
因此就将环形问题就转化成了线性问题：
在第一个位置分成两种情况：偷还是不偷。
接下来就是分析打家劫舍I问题了
1.状态表示
经验+题目要求
对于本题而言就是：
f[i]表示：选择到i位置时，偷nums[i]，此时的最大金额
g[i]表示：选择到i位置时，不偷nums[i]，此时的最大金额
2.状态转移方程
根据状态表示，分两种情况：
因此状态方程为：
f[i]=g[i-1]+nums[i]; g[i]=max(f[i-1],g[i-1]); max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1))
3.初始化
只有0位置会发生越界，初始化一下0位置即可
4.填表顺序
从左往右，两个表同时填
5.返回值
返回：
代码实现
动态规划的代码基本就是固定的四步：
1.创建dp表 2.初始化 3.填表 4.返回值
本题完整代码实现：
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; //创建dp表 int n=nums.size(); vector<int> f(n); vector<int> 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]); } };
打家劫舍I的完整代码如下：
class Solution { public: int rob(vector<int>& nums) { //创建dp表 int n=nums.size(); vector<int> f(n); vector<int> g(n); //初始化 f[0]=nums[0]; //填表 for(int i=1;i<n;i++) { f[i]=g[i-1]+nums[i]; g[i]=max(f[i-1],g[i-1]); } //返回值 return max(f[n-1],g[n-1]); } };
