###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 213. House Robber II

## [題目連結:] https://leetcode.com/problems/house-robber-ii/description/

## 題目:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are **arranged in a circle**. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight **without alerting the police**.

**Example 1:**

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

**Example 2:**

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

**Example 3:**

Input: nums = [1,2,3]
Output: 3

## 解題想法:
* 同概念基本題: [198. House Robber](/YIzmiuAqRfm6voICu36IXg)

* 此題目為: 小偷要搶錢，但是不能連續搶鄰居，且房屋頭尾視為相鄰，求能搶的最大值
* 分成兩個子問題:
* max(搶 0~n-2間 , 搶 1~n-1間)

## Python:

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)<2:
            return nums[0]
        return max(self.robMoney(nums[:-1]),self.robMoney(nums[1:]))
        
    def robMoney(self,nums):
        if len(nums)<2:
            return nums[0]
        dp=[0]*len(nums)
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp[i]=max(dp[i-1],nums[i]+dp[i-2])
        return dp[-1]

result = Solution()
nums = [1,2,3,1]
ans = result.rob(nums)
print(ans)

## C++:

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