# 213. House Robber II

### Leetcode

<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***.

&#x20;

**Example 1:**

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

**Example 2:**

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

**Example 3:**

<pre><code><strong>Input: nums = [1,2,3]
</strong><strong>Output: 3
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - DP**

思路跟 [198. House Robber](https://bcjohnblue.gitbook.io/leetcode/198.-house-robber) 一樣，差別在偷竊最後一家時，不能把偷竊第一家的金錢也算進去，因此原本的 DP 方程不能單純只記錄數字，而需要分別紀錄：

1. **有**偷過第一家的總金錢 (`first`)
2. **沒有**偷過第一家的總金錢 (`noFirst`)

所以一開始的 DP 方程就會長得像這樣：

```javascript
const dp = [{
    first: nums[0],
    noFirst: 0,
}];
```

```javascript
var rob = function (nums) {
    const dp = [{
        first: nums[0],
        noFirst: 0,
    }];
    let max = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const value = nums[i];
        if (i === 1) {
            // 第二家
            dp[i] = {
                first: Math.max(nums[0], nums[1]),
                noFirst: value,
            }
            max = Math.max(max, dp[i].first);
        } else if (i === nums.length - 1) {
            // 最後一家只能用 noFirst 的值判斷
            dp[i] = {
                noFirst: Math.max(dp[i - 2].noFirst + value, dp[i - 1].noFirst),
            }
            max = Math.max(max, dp[i].noFirst);
        } else {
            // 中間剩餘的其他家
            dp[i] = {
                first: Math.max(dp[i - 2].first + value, dp[i - 1].first),
                noFirst: Math.max(dp[i - 2].noFirst + value, dp[i - 1].noFirst),
            }
            max = Math.max(max, dp[i].first);
        }
    }

    return max;
};
```

* **方法二 - DP**

這題的關鍵是，偷過第一家就不能偷最後一家，偷最後一家就不能偷第一家，所以其實可以用 198. 求出的 DP 跑以下兩種狀況求出最多可偷竊的金錢

1. 偷第一家，不偷最後一家&#x20;

從 `DP[0]` 計算到 `DP[nums.length - 2]`

2. 不偷第一家，偷最後一家&#x20;

從 `DP[1]` 計算到 `DP[nums.length - 1]`

```javascript
var rob = function (nums) {
    // 改寫 198. 解法，多傳入 start, end
    var robHelper = function (nums, start, end) {
        if (nums[start] === undefined) {
            return 0;
        }

        const dp = [];
        dp[start] = nums[start];
        let max = nums[start];

        for (let i = start + 1; i < end; i++) {
            const value = nums[i];
            if (i === start + 1) {
                dp[i] = Math.max(nums[start], nums[start + 1]);
            } else {
                dp[i] = Math.max(dp[i - 2] + value, dp[i - 1]);
            }
            max = Math.max(max, dp[i]);
        }

        return max;
    };

    // 1. 偷第一家，不偷最後一家 
    const max1 = robHelper(nums, 0, nums.length - 1);
    // 2. 不偷第一家，偷最後一家
    const max2 = robHelper(nums, 1, nums.length);

    return Math.max(max1, max2);
};
```

**參考資料**

{% embed url="<https://leetcode.wang/leetcode-213-House-RobberII.html>" %}
