个人主页：Lei宝啊 

愿所有美好如期而遇

---

打家劫舍Ihttps://leetcode.cn/problems/Gu0c2T/打家劫舍IIhttps://leetcode.cn/problems/PzWKhm/

状态转移方程就是这样的：

• i位置选择偷f[i]：f[i] = g[i-1] + nums[i];
• i位置选择不偷g[i]：g[i] = max(f[i-1], g[i-1]);  

class Solution 
{
public:int rob(vector<int>& nums) {int num = nums.size();if(num == 0) return 0;vector<int> g(num), f(num);f[0] = nums[0], g[0] = 0;for(int i=1; i<num; i++){f[i] = g[i-1] + nums[i];g[i] = max(f[i-1], g[i-1]);}return max(f[num-1], g[num-1]);}
};

 

class Solution 
{
public:int massage(int lhs, int rhs, vector<int>& nums) {if(lhs > rhs) return 0;vector<int> g(nums.size()), f(nums.size());//这里不需要初始化f[lhs],因为f[i]的状态转移方程不会越界//而上面的f[0]需要初始化是因为f[0]的状态转移方程会越界，所以从1开始for(int i=lhs; i<=rhs; i++){f[i] = g[i-1] + nums[i];g[i] = max(f[i-1], g[i-1]);}return max(f[rhs], g[rhs]);}int rob(vector<int>& nums) {int n = nums.size();//偷int lhs = massage(2, n-2, nums) + nums[0];//不偷int rhs = massage(1, n-1, nums);return max(lhs, rhs);}   
};