RE4wppt.jpg
198. 打家劫舍
var rob = function(nums) {
let n = nums.length;
if(n === 0) {
return 0
}
if (n === 1) {
return nums[0]
}
let dp = new Array(n).fill(0);
dp[0] = nums[0]
dp[1] = Math.max(nums[0], nums[1])
for (let i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
}
return dp[n - 1];
};
213. 打家劫舍 II
let rob = function(nums) {
if (nums.length === 0) return 0
if (nums.length === 1) return nums[0]
// 定义动态方程
let dpHandle = function(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]
}
let ans1 = dpHandle(nums, 0, nums.length - 2)
let ans2 = dpHandle(nums, 1, nums.length - 1)
return Math.max(ans1, ans2)
}
337. 打家劫舍 III
const rob = 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);
};
