打家劫舍
力扣题目链接
dp含义：考虑偷下标为0-i的房间时，能偷的最大金额
递推公式：
偷或不偷当前房间：
偷：dp[i-2]+nums[i]。不能偷i-1房间的，因为相邻。
不偷：dp[i-1]
dp[i]=Max(dp[i-2]+nums[i],dp[i-1])
初始化：
由递推公式，可看出i>=2,因此需要初始化dp[0],dp[1]
dp[0]=nums[0],dp[1]=Max(nums[1],nums[0])
var rob = function(nums) {
let dp = [];
dp[0] = nums[0];
dp[1] = Math.max(nums[1], nums[0]);
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
};
打家劫舍II
与打家劫舍的区别：最后一个房间，若选择，则第一个房间不能选。
分析：
拆分成三种情况：
1.不考虑首位元素
- 不考虑尾元素
-
不考虑首元素
image.png
image.png
image.png
但2，3情况包含情况1。因此，最终所求应为2，3情况取最大值。
var rob = function(nums) {
console.log(robAss(nums.slice(1)))
console.log(robAss(nums.slice(0,nums.length-1)))
if(nums.length ===1){
return nums[0]
}
return Math.max(robAss(nums.slice(1)),robAss(nums.slice(0,nums.length-1)))
};
function robAss(nums){
const len = nums.length;
// dp数组初始化
const dp = [nums[0], Math.max(nums[0], nums[1])];
// 从下标2开始遍历
for (let i = 2; i < len; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[len - 1];
}
打家劫舍III
树形dp题目
力扣题目链接
- dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
确定遍历顺序 - 遍历顺序。后序遍历。 因为要通过递归函数的返回值来做下一步计算。
var rob = function(root) {
var postOrder = node=>{
if(!node) return [0,0]
let left= postOrder(node.left)
let right=postOrder(node.right)
Do = node.val+left[0]+right[0]
DoNot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return [DoNot,Do]
}
return Math.max(postOrder(root)[0],postOrder(root)[1])
};
