今天就是打家劫舍的一天,这个系列不算难,大家可以一口气拿下。
198.打家劫舍
视频讲解:https://www.bilibili.com/video/BV1Te411N7SX
https://programmercarl.com/0198.打家劫舍.html
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
const dp = new Array(nums.length);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
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];
};
213.打家劫舍II
视频讲解:https://www.bilibili.com/video/BV1oM411B7xq
https://programmercarl.com/0213.打家劫舍II.html
在一的基础上变了下
var numsDp = function(nums) {
const dp = new Array(nums.length);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
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];
};
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if (nums.length === 1) return nums[0]
const nums1 = numsDp(nums.slice(0, nums.length - 1));
const nums2 = numsDp(nums.slice(1, nums.length));
return Math.max(nums1, nums2);
};
337.打家劫舍III
视频讲解:https://www.bilibili.com/video/BV1H24y1Q7sY
https://programmercarl.com/0337.打家劫舍III.html
树形dp
/**
* 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 backtracing = (node) => {
if (node === null) {
return [0, 0];
}
let leftDp = backtracing(node.left);
let rightDp = backtracing(node.right);
const dp = [];
dp[0] = Math.max(leftDp[1],leftDp[0]) + Math.max(rightDp[1],rightDp[0]);
dp[1] = leftDp[0] + rightDp[0] + node.val;
return dp;
}
const dpRoot = backtracing(root);
return Math.max(dpRoot[0],dpRoot[1]);
};
标签:node,198,nums,随想录,https,打家劫舍,com,dp
From: https://www.cnblogs.com/yuanyf6/p/18264158