觀前提醒：

1. 我預設大家已經先思考並分析過題目，沒啥想法才開始 google 找解題靈感。若無，建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法。
2. 承上，既然已經有思考過了，那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了，那我可能解題想法 & 心得的部分就不會寫太多，免得干擾你的思考。
3. 所有解法都是已經取得系統的 Accepted，但或許不是最優解法，請多包涵。
4. 若對於解法不太懂，可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
5. 最後，歡迎在下面留言指教~教學相長才會進步歐~

題目

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 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 representing the amount of money of each house, determine 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:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

解題想法

這題直接破題的話，那就得要站在小偷的角度來看的話，有以下幾大重要先決條件：

• 千萬不能被警察抓到
• 要是直接"開箱"(?)相鄰兩個房子的話，警報器必響，警察一定到。

接下來，如果小偷要最大化自身獲利的話，他在面臨每一棟新房子時，一定會做出以下決策。
搶這棟房子(n)的話，他跟前第二棟(n-2)的房子的加總金額，能不能大於前第一棟房子(n-1)

p.s 順帶一提，我們還需要計算每間房子可以偷得多少錢，因此需要一個陣列來儲存偷到目前房子的最大獲利是多少。

大家一定會覺得，ㄟ真好像看起來很不直觀耶。
因為題目就說我們不能連續闖兩間空門啊，這樣會被抓包
接下來就讓我們實作看看囉~

CODE

var rob = function (nums) {
  // 處理 edge case
  if (nums === null || nums.length === 0) return 0;
  else if (nums.length === 1) {
    return nums[0];
  }
  //建立儲存最大獲利的陣列
  let runningTotal = [];
  runningTotal[0] = nums[0];
  runningTotal[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    // 最大金額   = Max(現在金額+前第二棟最大金額 ， 前一棟最大金額)
    runningTotal[i] = Math.max(
      nums[i] + runningTotal[i - 2],
      runningTotal[i - 1]
    );
  }
  return runningTotal[runningTotal.length - 1];
};

心得

綜上所述，這題可以簡化為：在給定一個陣列後，找出所有任兩數不相鄰的元素，加總後並求其最大值。再搭配貪婪演算法的概念，會更容易理解其核心思路。
希望這樣有幫助到大家~~

謝謝大家的收看，LeetCode 小學堂我們下次見~