题解 | #打家劫舍(二)#

class Solution {
  public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len + 3, 0); //dp[i]代表以第i个为打劫的结尾的最大数额
        for (int i = len - 2; i >= 0; i--) { //不选最后一个
            dp[i] = nums[i] + max(dp[i + 2], dp[i + 3]);
        }
        int res1 = max(dp[0], dp[1]);
        for (int i = len - 1; i >= 1; i--) { //不选第一个
            dp[i] = nums[i] + max(dp[i + 2], dp[i + 3]);
        }
        return max(res1, max(dp[1], dp[2]));
    }
};