---
# System prepended metadata

title: 0213. House Robber II
tags: [Leetcode, Dynamic Programming, Medium]

---

# 0213. House Robber II
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/house-robber-ii/
## 思路
考虑环的影响，首位和末位不能同时为yes。这说明至少有一个的选择是no。

(1) 如果首位我们选择no，那么从nums[1]到nums[n-1]的选择就没有环形的首尾制约，完全就是一个[0198. House Robber](https://hackmd.io/2t7kWFk_TVmewlzltG_Qaw)的问题。

(2) 如果末位我们选择no，那么从nums[0]到nums[n-2]的选择就没有环形的首尾制约，同样也是一个[0198. House Robber](https://hackmd.io/2t7kWFk_TVmewlzltG_Qaw)的问题。

我们将两种情况下的最优解再取最大值，就是答案。

注意，(1)和(2)并不是互斥的。他们是有交叠的。但是它们的并集一定是全集。
## Code
```java=
class Solution {
    public int rob(int[] nums) {
        // skip nums[0]
        if(nums.length==1) return nums[0];
        int rob = nums[1], norob = 0;
        int n = nums.length;
        for(int i=2; i<n; i++){
            int rob_temp = rob;
            rob = norob+nums[i];
            norob = Math.max(rob_temp, norob);
        }
        int ans = Math.max(rob, norob);
        
        //skip nums[n-1]
        rob = nums[0];
        norob = 0;
        for(int i=1; i<n-1; i++){
            int rob_temp = rob;
            rob = norob+nums[i];
            norob = Math.max(rob_temp, norob);
        }
        ans = Math.max(ans, Math.max(rob, norob));
        return ans;
    }
}
```