[leetcode - Bliend-75 ] 213. House Robber II (Medium)

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.

这题和 198. House Robber (Medium) 差不多但不同的点在于现在房子变成循环的，也就是说如果偷了第一间那么最后一间也不能偷，同理最后一间偷了则第一间不能偷。

Step

因为偷了第一间（从第一间开始）就不能偷最后一间，所以将最后一间移除掉并和 198. House Robber (Medium) 一样建立 移除掉最后一间房子 的 dp array

接着建立第二个 dp 是从略过第一间，如果略过第一间就可以偷到最后一间（从第二间开始），所以移除掉第一间并和198. House Robber (Medium) 一样建立 移除掉第一间房子 的 dp array

Create skipLastHouseDp

nums = [2] 则只有一个选项便是 2

---

nums = [2,7] 则有两个选项，第一个是去第一间拿到 1 块第二个是去第二间拿到 7 块，而 7 > 1 则将 7 放入 skipLastHouseDp 中代表 nums = [2,7] 时可以拿到最多的钱。

---

nums = [2,7,9] 有两个选项拿 9 和 7 之前的房子中最多钱的，因为 7 连着 9 所以要跳过 7 找 7 之前的最大值
不拿 9 而拿 9 之前的房子中最多钱的，而 9 之前最多钱的在 2 (nums = [2,7]) 已经算过并放进 dp 里面了
方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9] 时可以拿得最多钱

---

nums = [2,7,9,3] 有两个选项拿 3 和 9 之前的房子 [2,7] 中最多钱的值相加，因为 9 连着 3 所以要跳过 9 找 9 之前的最大值，而 9 之前的最大值在 2 (nums = [2,7]) 已经算过并放进 dp 里了
不拿 3 而拿 3 之前的房子 [2,7,9] 中最多钱的，而 3 之前最多钱的已经在 3 (nums = [2,7,9]) 中算过并放进 dp 中了
方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9,3] 时可以拿得最多钱

---

Create skipFirstHouseDp

因为要略过第一间房子，所以要从第二间房子开始，而略过第一间房子所以 skipFirstHouseDp 也从 index = 2 开始。

---

nums = [7] 则只有一个选项便是 7

---

nums = [7,9] 则有两个选项，第一个是去第一间拿到 7 块第二个是去第二间拿到 9 块，而 9 > 7 则将 9 放入 skipFirstHouseDp 中代表 nums = [7,9] 时可以拿到最多的钱。

---

nums = [7,9,3] 有两个选项拿 3 和 9 之前的房子中最多钱相加，因为 9 连着 3 所以要跳过 9 找 9 之前的最大值
不拿 3 而拿 3 之前的房子中最多钱的，而 3 之前最多钱的在 3 (nums = [7,9]) 已经算过并放进 dp 里面了
方法一和方法二的最大值放入 dp 中表示 nums = [7,9,3] 时可以拿得最多钱

---

nums = [7,9,3,1] 有两个选项拿 1 和 3 之前的房子中最多钱相加，因为 3 连着 1 所以要跳过 3 找 3 之前的最大值，而 nums = [7,9] 在 3 已经算过并放进 skipFirstHouseDp 中了
不拿 1 而拿 1 之前的房子中最多钱的，而 1 之前最多钱的在 4 (nums = [7,9,3]) 已经算过并放进 dp 里面了
方法一和方法二的最大值放入 dp 中表示 nums = [7,9,3,1] 时可以拿得最多钱

---

Answer

比较 skipLastHouseDp 和 skipFirstHouseDp 中最大值便是解答。

Coding

/** * @param {number[]} nums * @return {number} */var rob = function(nums) {    if (nums.length === 1) return nums[0];    if (nums.length === 2) return Math.max(nums[0], nums[1]);    const skipLastHouse = [];    skipLastHouse[0] = nums[0];    skipLastHouse[1] = Math.max(nums[0], nums[1]);    for(let i = 2; i < nums.length - 1; i++) {        skipLastHouse[i] = Math.max(nums[i] + skipLastHouse[i - 2], skipLastHouse[i - 1]);    }    const skipFirstHouse = [];    skipFirstHouse[1] = nums[1];    skipFirstHouse[2] = Math.max(nums[1], nums[2]);    for(let i = 3; i < nums.length; i++) {        skipFirstHouse[i] = Math.max(nums[i] + skipFirstHouse[i - 2], skipFirstHouse[i - 1]);    }    return Math.max(skipLastHouse[skipLastHouse.length - 1], skipFirstHouse[skipFirstHouse.length - 1]);};

Time complexity: O(n)