LeetCode 213 House Robber II

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-02-20 10:39:24
    编辑于：2022-02-20 11:04:14
    浏览量：728

概述

https://leetcode.com/problems/house-robber-ii/

动态规划法（转换为直线房子群）

对于第一个房子：

不抢，则和之前直线时的情况一致；
抢，则我们不能再抢最后一个了，我们可以选择将最后一个设为 0，重新跑一遍。

class Solution {
public:
    vector<int> dp;
    int rob(vector<int>& nums) {
        dp.resize(nums.size(), -1);
        int ans = helper(nums, 1);
        nums[nums.size() - 1] = 0;
        fill(dp.begin(), dp.end(), -1);
        ans = max(ans, helper(nums, 0));
        return ans;
    }
    
    int helper(vector<int>& nums, int i) {
        if (i >= nums.size()) return 0;
        if (dp[i] != -1) return dp[i];
        dp[i] = max(nums[i] + helper(nums, i + 2), helper(nums, i + 1));
        return dp[i];
    }
};

上面的代码忽视了 size 为 1 时的 case，此时由于你把唯一的元素置为了 0，导致最终结果是 0，因此需要加上：

if (nums.size() == 1) return nums[0];

上面的方法构建了两次 dp 数组，我看了 labudadong 的解法，也是如此，无非是迭代形式。其状态定义为抢从 i 到 j 的房子。

Links: leetcode-213-house-robber-ii