打家劫舍
leetcode：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
js
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
思路
- 偷第一间房：
nums[0] - 偷第二间房：
Math.max(nums[0], nums[1]) - 偷第三间房：
Math.max(nums[1], nums[0] + nums[2]); - 偷第 i 间房：
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
代码
js
var rob = function (nums) {
let dp = [nums[0], Math.max(nums[0], nums[1])];
let len = nums.length;
for (let i = 2; i < len; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[len - 1];
};
打家劫舍 II
leetcode：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
js
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
输入：nums = [1,2,3]
输出：3
思路
对于一个数组，按照题意也就是首尾不能同时存在，那么拆分两种情况比较就可以了比如：
js
[1, 2, 3, 4, 5]
情况1 不包含尾元素 [1, 2, 3, 4] 最大值 2 + 4 = 6；
情况2 包含尾元素 [2, 3, 4, 5] 最大值 3 + 5 = 8;
那么取最大值即可！
代码
js
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
let len = nums.length;
if (len === 0) return 0;
if (len === 1) return nums[0];
function fn(nums) {
let _len = nums.length;
let dp = [nums[0], Math.max(nums[0], nums[1])];
for (let i = 2; i < _len; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[_len - 1];
}
return Math.max(fn(nums.slice(0, len - 1)), fn(nums.slice(1)));
};
打家劫舍 III
leetcode：小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回在不触动警报的情况下 ，小偷能够盗取的最高金额。
js
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
js
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
思路
这里刚开始做的时候，存在误区，认为进行层序遍历后，再通过 dp 进行计算最大值。如下（不通过的）：
js
var rob = function (root) {
if (!root) return 0;
let nums = [];
// 二叉树的层序遍历
let queue = [root];
while (queue.length) {
let len = queue.length;
let sum = 0;
for (let i = 0; i < len; i++) {
let node = queue.shift();
sum += node.val;
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
nums.push(sum);
}
// 打家劫舍
function robRoom(nums) {
let len = nums.length;
let dp = [nums[0], Math.max(nums[0], nums[1])];
for (let i = 2; i < len; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[len - 1];
}
return robRoom(nums);
};
更多思路可以见 四种写法：递归、记忆化递归、树形 DP、降维优化 | 337. 打家劫舍 III
这里理解到递归思路：
打不打劫根节点，会影响打劫一棵树的收益：
- 打劫根节点，则不能打劫左右子节点，但是能打劫左右子节点的四个子树（如果有）。
- 不打劫根节点，则能打劫左子节点和右子节点，收益是打劫左右子树的收益之和。
代码
js
var rob = function (root) {
let memo = new Map(); // 这里没剪枝，如果不加 map 测试用例通过不了，超时了！
function dfs(root) {
if (!root) return 0;
if (memo.has(root)) return memo.get(root);
// 1. 打劫节点下的左右子树
const value1 = dfs(root.left) + dfs(root.right);
// 2. 打结根节点 + 叶子节点
const value2 =
root.val +
// 左叶子结点
dfs(root.left?.left) +
dfs(root.left?.right) +
// 右叶子结点
dfs(root.right?.left) +
dfs(root.right?.right);
const res = Math.max(value1, value2);
// 保存当前子树的计算结果
memo.set(root, res);
return res;
}
return dfs(root);
};