当前位置: 首页 > news >正文

企业网站程序源码重庆网络推广公司

企业网站程序源码,重庆网络推广公司,网上二手书网站开发中的问题和展望,wordpress动漫博客模板198. 打家劫舍 当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。 递归五部曲: dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。决定dp[i]的因素就是第i房间偷还是不偷。 如果偷第i房间&…

198. 打家劫舍

当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。

递归五部曲:

  1. dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
  2. 决定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])
  1. 递推公式的基础就是dp[0] 和 dp[1]。从dp[i]的定义上来讲,dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1])
  2. 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

成环的话主要有如下三种情况:

  1. 考虑不包含首尾元素
  2. 考虑包含首元素,不包含尾元素
  3. 考虑包含首元素,不包含尾元素

情况二 和 情况三 都包含了情况一了,所以只考虑情况二和情况三就可以了。剩下的就和普通的打家劫舍一样了。

/*** @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的数组,记录当前节点偷与不偷所得到的的最大金钱。

递归三部曲:

  1. 确定递归函数的参数和返回值
    要求一个节点 偷与不偷的两个状态所得到的金钱,那么返回值就是一个长度为2的数组。
    dp数组(dp table)以及下标的含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。
  2. 确定终止条件
    在遍历的过程中,如果遇到空节点的话,很明显,无论偷还是不偷都是0,所以就返回
  3. 确定遍历顺序
    首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。
    通过递归左节点,得到左节点偷与不偷的金钱。
    通过递归右节点,得到右节点偷与不偷的金钱。
  4. 确定单层递归逻辑
    如果是偷当前节点,那么左右孩子就不能偷;
    如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的
  5. 举例推导dp数组

最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。

/*** 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 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.dt0577.cn/news/3132.html

相关文章:

  • 网站开发策划个人简历百度一下 你就知道官网 新闻
  • 男女做暧昧试看网站快速整站优化
  • 电子商务网站建设与管理 李建忠谷歌推广代理公司
  • 上海手机网站建设电话北京十大最靠谱it培训机构
  • 网站导航的交互怎么做济南百度开户电话
  • 免费传媒手机网站seo免费软件
  • 黄石规划建设局网站微商引流一般用什么软件
  • 是一个网站或站点的第一个网页百度关键词排名提升工具
  • 广告投放代理商seo怎么收费的
  • 南京做网站seo淘宝排名查询
  • 刚开始做网站要传数据库吗新产品推广策划方案
  • 男人与女人做视频网站电商怎么做营销推广
  • 做网站页面设计报价系统优化助手
  • 做代码的网站百度学术免费查重入口
  • 做电子杂志用什么网站广州seo服务
  • 最近新闻报道seo推广软件排行榜
  • 中国建设教育协会是什么网站推广技术
  • 企业网站建设找外包公司做营业推广是一种什么样的促销方式
  • 魔兽7.2国内做插件网站下百度安装
  • 网站建设需求量大3天引流800个人技巧
  • 做网站服务器和域名站长工具推荐网站
  • 网站备案号被注销最新足球赛事
  • 做公司网站需要准备什么国际要闻
  • PHP视频类网站应该怎么做网络服务有哪些
  • 建筑公司网址网站搜索排名优化软件
  • 福建省网站备案用户注销(删除)备案申请表安全优化大师下载
  • 缙云做网站推广平台软件有哪些
  • 内蒙古地区做推广网站免费网站推广网站短视频
  • 郑州市城乡建设委员会网站四川整站优化关键词排名
  • 网站备案 网站建设方案书长沙seo智优营家