leetcode 213 打家劫舍II-蒲公英云

leetcode 213 打家劫舍II

题目

题目：213. 打家劫舍 II

参考题解：打家劫舍II-代码随想录、打家劫舍II-力扣官方题解

提交代码

我没想出来，看的答案。

在leetcode 198 打家劫舍基础上。头尾不能同时获取。

如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。

emm，上面的思路直觉上是对的。但是，没有经过数学证明。

// 我直接用了leetcode 198的代码；本题可以不用进行数组拷贝，传递下标即可。
class Solution {
public:
    int rob_part(vector<int>& nums) {
        // 递推公式:dp[i] = max(dp[i-1],dp[i-2]+nums[i])
        // 题目限定，至少有一个元素
        if(nums.size() <= 2){
            if(nums.size() == 1)
                return nums[0];
            else if(nums.size() == 2)
                return max(nums[0], nums[1]);
            return 0;
        }
        //dp[i]表示[0,i]闭区间，能获得的最大财富
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i=2; i<nums.size(); i++)
            dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
        return dp[nums.size()-1];
    }
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return max(nums[0], nums[1]);
        vector<int> left_nums(nums.begin(),nums.end()-1);
        vector<int> right_nums(nums.begin()+1,nums.end());
        return max(rob_part(left_nums), rob_part(right_nums));
    }
};