213. 打家劫舍 II

原题链接：213. 打家劫舍 II

solution:

这题和打家劫舍的思路是一样的.

状态表示：dp[i]表示从前1~i个房子中选择,获得的最大金额

属性：求解的最大值

状态计算：以选或不选i进行判断。

①不选择i的时候:那么问题转化为从前1~i - 1中进行选择，获得的最大值dp[i - 1]

②选择i的时候：由于不能选择相邻的房子,因此最大值为dp[i - 2] + nums[i]

综上所述状态转移方程：dp[i] = max(dp[i - 1],dp[i - 2] + nums[i]]

！！！本题还有个特殊条件房间成一个环状,因此第一个房子和最后一个房子不能同时选择，因此只需要分情况进行讨论就行,分为dp1[1 ~ i - 1]和dp2[2 ~ i]，最后取最大值

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(!n) return 0;
        if(n == 1) return nums[0];
        vector<int> dp1(n + 1),dp2(n + 1);

        dp1[1] = nums[0];
        for(int i = 2;i <= n - 1;i++) {
            dp1[i] = dp1[i - 1];
            dp1[i] = max(dp1[i],dp1[i - 2] + nums[i - 1]);
        }

        dp2[2] = nums[1];
        for(int i = 3;i <= n;i++) {
            dp2[i] = dp2[i - 1];
            dp2[i] = max(dp2[i],dp2[i - 2] + nums[i - 1]);
        }
        return max(dp1[n - 1],dp2[n]);
    }
};