198. 打家劫舍

當前房屋偷與不偷取決于 前一個房屋和前兩個房屋是否被偷了。

遞歸五部曲：

1. dp[i]：考慮下標i（包括i）以內的房屋，最多可以偷竊的金額為dp[i]。
2. 決定dp[i]的因素就是第i房間偷還是不偷。

• 如果偷第i房間，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考慮的，找出 下標i-2（包括i-2）以內的房屋，最多可以偷竊的金額為dp[i-2] 加上第i房間偷到的錢。
• 如果不偷第i房間，那么dp[i] = dp[i - 1]，即考 慮i-1房
  然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

3. 遞推公式的基礎就是dp[0] 和 dp[1]。從dp[i]的定義上來講，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1])
4. dp[i] 是根據dp[i - 2] 和 dp[i - 1] 推導出來的，那么一定是從2開始從前到后遍歷

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

213. 打家劫舍II

成環的話主要有如下三種情況：

1. 考慮不包含首尾元素
2. 考慮包含首元素，不包含尾元素
3. 考慮包含首元素，不包含尾元素

情況二 和 情況三 都包含了情況一了，所以只考慮情況二和情況三就可以了。剩下的就和普通的打家劫舍一樣了。

/*** @param {number[]} nums* @return {number}*/
var rob = function (nums) {const n = nums.lengthif (n === 0) return 0if (n === 1) return nums[0]const result1 = robRange(nums, 0, n - 2)const result2 = robRange(nums, 1, n - 1)return Math.max(result1, result2)
};const robRange = (nums, start, end) => {if (end === start) return nums[start]const dp = new Array(nums.length).fill(0)dp[start] = nums[start]dp[start + 1] = Math.max(nums[start], nums[start + 1])for (let i = start + 2; i <= end; i++) {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])}return dp[end]
}

337. 打家劫舍III

使用一個長度為2的數組，記錄當前節點偷與不偷所得到的的最大金錢。

遞歸三部曲：

1. 確定遞歸函數的參數和返回值
   要求一個節點 偷與不偷的兩個狀態所得到的金錢，那么返回值就是一個長度為2的數組。
   dp數組（dp table）以及下標的含義：下標為0記錄不偷該節點所得到的的最大金錢，下標為1記錄偷該節點所得到的的最大金錢。
2. 確定終止條件
   在遍歷的過程中，如果遇到空節點的話，很明顯，無論偷還是不偷都是0，所以就返回
3. 確定遍歷順序
   首先明確的是使用后序遍歷。 因為要通過遞歸函數的返回值來做下一步計算。
   通過遞歸左節點，得到左節點偷與不偷的金錢。
   通過遞歸右節點，得到右節點偷與不偷的金錢。
4. 確定單層遞歸邏輯
   如果是偷當前節點，那么左右孩子就不能偷；
   如果不偷當前節點，那么左右孩子就可以偷，至于到底偷不偷一定是選一個最大的
5. 舉例推導dp數組

最后頭結點就是 取下標0 和 下標1的最大值就是偷得的最大金錢。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var rob = function (root) {const postOrder = node => {// 遞歸出口if (!node) return [0, 0];// 遍歷左子樹const left = postOrder(node.left);// 遍歷右子樹const right = postOrder(node.right);// 不偷當前節點，左右子節點都可以偷或不偷，取最大值const DoNot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);// 偷當前節點，左右子節點只能不偷const Do = node.val + left[0] + right[0];// [不偷，偷]return [DoNot, Do];};const res = postOrder(root);// 返回最大值return Math.max(...res);
};