leetcode 213. House Robber II

Description:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [0]
Output: 0

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

分析：基础dp
从最开始的房屋开始打劫
total记录打劫当前房屋的最大收益
状态转移方程：total[i] = nums[i]+max(total[i-2],total[i-3]);

但有一点小弯:第一个和最后一个房屋不可以同时打劫。
那么需要dp两遍，第一遍不包含第一个房屋，第二遍不包含最后一个房屋，然后两次取最大值即为答案。

class Solution {
public:
    vector<int> total;
    int rob(vector<int>& nums) {
        int ans = nums[0];
        if(nums.size() < 4){
            for(int i = 1; i < nums.size(); ++i){
                if(nums[i] > ans) ans = nums[i];
            }
            return ans;
        }
        int ans2 = nums[1];
        total.resize(nums.size());
        total[0] = nums[0];
        total[1] = nums[1];
        total[2] = nums[0]+nums[2];
        for(int i = 3; i < nums.size()-1; ++i){
            total[i] = nums[i]+max(total[i-2],total[i-3]);
        }
        ans = max(total[total.size()-2],total[total.size()-3]);
        total[2] = nums[2];
        total[3] = nums[1]+nums[3];
        for(int i = 4; i < nums.size(); ++i){
            total[i] = nums[i]+max(total[i-2],total[i-3]);
        }
        ans2 = max(total[total.size()-1],total[total.size()-2]);
        return max(ans,ans2);
    }
};