198 House Robber

DP

0~n-1     ans=dp[n-1]

dp[i] = max(dp[i-2]+nums[i], dp[i-1])  i>=2

如果要输出偷了那些房子，可以用backpointer来记录 argmax dp[i]，即记录dp[i] 是通过 i-1 还是 i-2 得到最大值的。

所有dp问题都可以用backpointer来找.

class Solution {public:    int rob(vector
     
      & nums) {        int n=nums.size();        if (n==0) return 0;        if (n==1) return nums[0];        if (n==2) return max(nums[0],nums[1]);                vector
      
        dp(n);        vector
       
         bp(n); //record the the previous index : argmax dp[i]        dp[0] = nums[0]; bp[0]=-1;        dp[1] = max(nums[0],nums[1]); bp[1]=-1;        for (int i=2;i
        
         =dp[i-1]){                dp[i] = dp[i-2]+nums[i];                bp[i] = i-2;            }else{                dp[i] = dp[i-1];                bp[i] = i-1;            }        }        vector
         
           res;        int pos=bp[n-1]==n-2?n-2:n-1;        while (pos!=-1){            res.push_back(nums[pos]);            pos = bp[pos];        }        reverse(res.begin(),res.end());        for (auto x:res) cout<
          
           <<' '; return dp[n-1]; }};
          
         
        
       
      
     

 

  

213 House Robber II

Since we cannot rob nums[0] and nums[n-1] at the same time, we can divide this problem into two cases:

not rob nums[0]

not rob nums[n-1]

and the answer is the maximum one.

C++ stl vector可以用 vector<int> nums1(nums.begin(), nums.end())来初始化 比较实用