题目一
题目链接：打家劫舍I 思路 小偷每到一初，都可以选择对这个位置偷还是不偷，所以，这次我们需要定义两个表
小Tips：针对这种情况，一般上都需要定义两个dp表，因为每一个位置我们都可以选择。
- 状态表示：
- f[i]:表示第i家小偷偷，得到的总金额。
- g[i]:表示第i家小偷不偷，得到的总金额。
- 状态转移方程
- f[i]：f[i]=g[i-1] nums[i]。
- 第i家偷的话，就意味着第i-1家不可以偷。
- g[i]：g[i]=max(f[i-1],g[i-1]）
- 不偷第i家的话，那么就要看第i-1家是偷还是不偷了。
代码表示：
- f[i]：f[i]=g[i-1] nums[i]。
class Solution {
public:
int rob(vector<int>& nums) {
//创建dp表
//初始化
//填表
//返回值
int ret=nums.size();
if(ret==1) return nums[0];
vector<int> f(ret);//此位置选
auto g=f;//此位置不选
f[0]=nums[0];
g[0]=0;
int i=0;
for(i=1;i<ret;i )
{
f[i]=g[i-1] nums[i];
g[i]=max(f[i-1],g[i-1]);
}
return max(f[ret-1],g[ret-1]);
}
};题目二
题目链接：打家劫舍二 思路： 这道题和上一道题的不同之处在于：本道题的题目设定是：最后一家和第一家是连着的，也就是说第一家和最后一家只可以偷一家。
所以我们要封装一个函数，以第一家偷还是不偷为两种不同的情况进行划分。
代码语言：javascript复制class Solution {
public:
int rob1(int left,int right,vector<int>&nums)
{
if(left>right) return 0;
if(left==right) return nums[left];
int ret=nums.size();
vector<int> f(ret);//改位置要抢劫
auto g=f;//该位置不盗
for(int i=left;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]);
}
int rob(vector<int>& nums) {
int ret=nums.size();
return max(rob1(1,ret-1,nums),rob1(2,ret-2,nums) nums[0]);
}
};
