题解 | 打家劫舍(二)

class Solution {
public:
 /*
  有三种情况：偷第一家不偷最后一家；偷最后一家不偷第一家；首末两家都不偷；
  动态规划进行， 分两种情况求解， 第三种情况包含
*/
    int rob(vector<int>& nums) {
       vector<int> dp(nums.size()+1, 0);

        int res =nums[0];
        dp[1] = nums[0];  //选择偷第一家
       for(int i=2; i<nums.size(); i++){  //最后一家不遍历
            dp[i] = max( dp[i-1], nums[i-1]+dp[i-2] );
            res = max(res, dp[i]);
       }

       dp.clear();
       dp[0] = 0, dp[1] = 0;  //第一家不偷
        for(int i=2; i<=nums.size(); i++){
            dp[i] = max( dp[i-1], dp[i-2]+nums[i-1]);
            res = max(res, dp[i]);
        }

       return res;
    }
};