出處： https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/576/
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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 = [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 2:
Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 400
LeetCode 做到現在，最喜歡的一題。 大意是說你是一個搶匪，要去洗劫別人家，但每一個家裡都有安裝自動報警系統，所以作案之間必須至少間隔洗劫一次的時間。題目給的陣列數字代表每間房子的存金，試著計算出最高能得手的金額。
var rob = function(nums) {
// 當目標數小於等於 2 時，直接選金額高的那間
if (nums.length <= 2) return Math.max(...nums)
const robbed = Array(nums.length)
// 第 1 間，直接帶第一間的金額
robbed[0] = nums[0]
// 第 2 間，第 1 和 第 2 選最高的
robbed[1] = Math.max(nums[0], nums[1])
// 從第三次開始，每一次的決定需要參考前兩次的最高可能金額來判斷
for (let i = 2; i < nums.length; i++) {
// 目前這間 ( i ) 的金額 + 相隔 1 次 ( i - 2) 時的最高金額 vs. 上一次 （i - 1）時的最高金額的最大值
robbed[i] = Math.max(robbed[i - 2] + nums[i], robbed[i - 1])
}
return robbed[nums.length - 1]
};思路
一開始，我想的超級複雜，本來還想用 linked list 的方式找出所有可能性。後來看了討論區，理解之後之後，得到心得如下：
- 不用找出所有可能性，目標是放在最高可得手的金額
- 當目標數小於等於 2 時，直接選金額高的那間
- 從第三次開始，走一個迴圈，每一次的決定需要參考前兩次的最高可能金額來判斷
- 判斷方式 – 目前這間 ( i ) 的金額 + 相隔 1 次 ( i – 2) 時的最高金額 vs. 上一次 （i – 1）時的最高金額的最大值
