213. House Robber II

[Tcdian]

213. House Robber II

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 a list of non-negative integers 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 = [0]
Output: 0

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

[Tcdian]

Solution

• TypeScript Solution

function rob(nums: number[]): number {
    const len = nums.length;
    if (len < 3) {
        return dpRob(nums);
    }
    return Math.max(dpRob(nums.slice(0, nums.length - 1)), dpRob(nums.slice(1)));

    function dpRob(nums: number[]): number {
        const len = nums.length;
        if (len === 0) {
            return 0;
        }
        let dp = new Array(len);
        for (let i = 0; i < len; i++) {
            if (i === 0) {
                dp[i] = nums[i];
            } else if (i === 1) {
                dp[i] = Math.max(nums[i], dp[i - 1]);
            } else {
                dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
            }
        }
        return dp[len - 1];
    }
};