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.

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

解答

• 方法一 - DP

思路跟 198. House Robber 一樣，差別在偷竊最後一家時，不能把偷竊第一家的金錢也算進去，因此原本的 DP 方程不能單純只記錄數字，而需要分別紀錄：

1. 有偷過第一家的總金錢 (first)

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

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

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

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. 偷第一家，不偷最後一家

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

1. 不偷第一家，偷最後一家

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

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);
};

參考資料

213. House Robber II · leetcodeleetcode.wang