Leetcode 213 House Robber 2

Leetcode 213 题

Difficulty:Medium

Tag: Dynamic Programming

House Robber 2

题目原址：https://leetcode.com/problems/house-robber-ii/?tab=Description

This is an extension of House Robber. After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

这是 House Robber 的拓展版，现在的情况是所有的房子围成了一个圈，由于不能抢相邻两家的限制，第一家和最后一家只能选择一家，而不能同时选。

思路

既然 第一家 和 最后一家 只能选一个，那分别将第一家和最后一家去掉，此时两种情况均满足House Robber的情况，然后按照House Robber中的算法分别计算一次，然后取最大值。

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() <= 1) return nums.empty() ? 0 : nums[0];
        if(nums.size() == 2) return max(nums[0], nums[1]);
        return max(rob(nums, 0, nums.size() - 1), rob(nums, 1, nums.size()));
    }
    
    int rob(vector<int>& nums, int left, int right)
    {
        vector<int> dp(right, 0);
        dp[left] = nums[left];
        dp[left + 1] = max(nums[left], nums[left + 1]);
        for(int i = left + 2; i < right; i++)
        {
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
        }
        return dp.back();
    }
};