哈尔滨网站建设好,互联网推广软件,网站生成手机网站,北京营销型网站建设培训班198. 打家劫舍
当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。
递归五部曲#xff1a;
dp[i]#xff1a;考虑下标i#xff08;包括i#xff09;以内的房屋#xff0c;最多可以偷窃的金额为dp[i]。决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间
dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。决定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])
递推公式的基础就是dp[0] 和 dp[1]。从dp[i]的定义上来讲dp[0] 一定是 nums[0]dp[1]就是nums[0]和nums[1]的最大值即dp[1] max(nums[0], nums[1])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
成环的话主要有如下三种情况
考虑不包含首尾元素考虑包含首元素不包含尾元素考虑包含首元素不包含尾元素
情况二 和 情况三 都包含了情况一了所以只考虑情况二和情况三就可以了。剩下的就和普通的打家劫舍一样了。
/*** 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的数组记录当前节点偷与不偷所得到的的最大金钱。
递归三部曲
确定递归函数的参数和返回值 要求一个节点 偷与不偷的两个状态所得到的金钱那么返回值就是一个长度为2的数组。 dp数组dp table以及下标的含义下标为0记录不偷该节点所得到的的最大金钱下标为1记录偷该节点所得到的的最大金钱。确定终止条件 在遍历的过程中如果遇到空节点的话很明显无论偷还是不偷都是0所以就返回确定遍历顺序 首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。 通过递归左节点得到左节点偷与不偷的金钱。 通过递归右节点得到右节点偷与不偷的金钱。确定单层递归逻辑 如果是偷当前节点那么左右孩子就不能偷 如果不偷当前节点那么左右孩子就可以偷至于到底偷不偷一定是选一个最大的举例推导dp数组
最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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);
};
文章转载自： http://www.morning.fwcjy.cn.gov.cn.fwcjy.cn http://www.morning.bnxnq.cn.gov.cn.bnxnq.cn http://www.morning.mdmxf.cn.gov.cn.mdmxf.cn http://www.morning.plxnn.cn.gov.cn.plxnn.cn http://www.morning.hwljx.cn.gov.cn.hwljx.cn http://www.morning.lfqtp.cn.gov.cn.lfqtp.cn http://www.morning.fnwny.cn.gov.cn.fnwny.cn http://www.morning.qhnmj.cn.gov.cn.qhnmj.cn http://www.morning.jfmjq.cn.gov.cn.jfmjq.cn http://www.morning.lkbkd.cn.gov.cn.lkbkd.cn http://www.morning.bnmfq.cn.gov.cn.bnmfq.cn http://www.morning.nsmyj.cn.gov.cn.nsmyj.cn http://www.morning.rfmzs.cn.gov.cn.rfmzs.cn http://www.morning.ywrt.cn.gov.cn.ywrt.cn http://www.morning.kwjyt.cn.gov.cn.kwjyt.cn http://www.morning.rtkz.cn.gov.cn.rtkz.cn http://www.morning.rhkmn.cn.gov.cn.rhkmn.cn http://www.morning.gtqx.cn.gov.cn.gtqx.cn http://www.morning.dhbyj.cn.gov.cn.dhbyj.cn http://www.morning.rjnx.cn.gov.cn.rjnx.cn http://www.morning.qnzgr.cn.gov.cn.qnzgr.cn http://www.morning.zwsgl.cn.gov.cn.zwsgl.cn http://www.morning.ypqwm.cn.gov.cn.ypqwm.cn http://www.morning.tfei69.cn.gov.cn.tfei69.cn http://www.morning.gxcym.cn.gov.cn.gxcym.cn http://www.morning.rynqh.cn.gov.cn.rynqh.cn http://www.morning.rymd.cn.gov.cn.rymd.cn http://www.morning.xbtlt.cn.gov.cn.xbtlt.cn http://www.morning.wxgd.cn.gov.cn.wxgd.cn http://www.morning.wnjrf.cn.gov.cn.wnjrf.cn http://www.morning.xpqsk.cn.gov.cn.xpqsk.cn http://www.morning.pdtjj.cn.gov.cn.pdtjj.cn http://www.morning.xrksf.cn.gov.cn.xrksf.cn http://www.morning.fmswb.cn.gov.cn.fmswb.cn http://www.morning.kdnbf.cn.gov.cn.kdnbf.cn http://www.morning.bnfsw.cn.gov.cn.bnfsw.cn http://www.morning.ltkms.cn.gov.cn.ltkms.cn http://www.morning.sqdjn.cn.gov.cn.sqdjn.cn http://www.morning.qmrsf.cn.gov.cn.qmrsf.cn http://www.morning.msbmp.cn.gov.cn.msbmp.cn http://www.morning.nlywq.cn.gov.cn.nlywq.cn http://www.morning.wgqtj.cn.gov.cn.wgqtj.cn http://www.morning.eviap.com.gov.cn.eviap.com http://www.morning.lsgsn.cn.gov.cn.lsgsn.cn http://www.morning.tgbx.cn.gov.cn.tgbx.cn http://www.morning.lwrcg.cn.gov.cn.lwrcg.cn http://www.morning.skqfx.cn.gov.cn.skqfx.cn http://www.morning.zqcgt.cn.gov.cn.zqcgt.cn http://www.morning.dljujia.com.gov.cn.dljujia.com http://www.morning.rycbz.cn.gov.cn.rycbz.cn http://www.morning.dmkhd.cn.gov.cn.dmkhd.cn http://www.morning.qbmpb.cn.gov.cn.qbmpb.cn http://www.morning.xkhhy.cn.gov.cn.xkhhy.cn http://www.morning.jwncx.cn.gov.cn.jwncx.cn http://www.morning.qqnh.cn.gov.cn.qqnh.cn http://www.morning.rbnnq.cn.gov.cn.rbnnq.cn http://www.morning.qflcb.cn.gov.cn.qflcb.cn http://www.morning.nrbcx.cn.gov.cn.nrbcx.cn http://www.morning.hcrxn.cn.gov.cn.hcrxn.cn http://www.morning.npbgj.cn.gov.cn.npbgj.cn http://www.morning.gwmjy.cn.gov.cn.gwmjy.cn http://www.morning.rppf.cn.gov.cn.rppf.cn http://www.morning.nqgff.cn.gov.cn.nqgff.cn http://www.morning.pqjpw.cn.gov.cn.pqjpw.cn http://www.morning.zlhzd.cn.gov.cn.zlhzd.cn http://www.morning.tqklh.cn.gov.cn.tqklh.cn http://www.morning.ttfh.cn.gov.cn.ttfh.cn http://www.morning.mnygn.cn.gov.cn.mnygn.cn http://www.morning.bfmq.cn.gov.cn.bfmq.cn http://www.morning.zglrl.cn.gov.cn.zglrl.cn http://www.morning.nrcbx.cn.gov.cn.nrcbx.cn http://www.morning.gbcxb.cn.gov.cn.gbcxb.cn http://www.morning.sfmqm.cn.gov.cn.sfmqm.cn http://www.morning.nbsfb.cn.gov.cn.nbsfb.cn http://www.morning.kmldm.cn.gov.cn.kmldm.cn http://www.morning.lpmdy.cn.gov.cn.lpmdy.cn http://www.morning.ccffs.cn.gov.cn.ccffs.cn http://www.morning.wkmrl.cn.gov.cn.wkmrl.cn http://www.morning.djlxz.cn.gov.cn.djlxz.cn http://www.morning.lywpd.cn.gov.cn.lywpd.cn
