LeetCode 213 House Robber II

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

概述

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

动态规划法(转换为直线房子群)

对于第一个房子:

  1. 不抢,则和之前直线时的情况一致;
  2. 抢,则我们不能再抢最后一个了,我们可以选择将最后一个设为 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 的房子。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/