day52 动态规划part9

2024-03-27 02:04
文章标签 动态 规划 day52 part9

本文主要是介绍day52 动态规划part9,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

198. 打家劫舍

中等
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

思路

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution {public int rob(int[] nums) {// 如果只有一间房或0间房:if (nums.length == 0) return 0;  // 如果没有房屋,返回0if (nums.length == 1) return nums[0]; // 如果只有一个房屋,返回其金额int[] dp = new int [nums.length]; // dp[i] 表示前i个屋子能偷到的最大金额, 即偷 [0..k) 房间中的最大金额,注意是从0算起,所以不包含kdp[0] = nums[0];  // 将dp的第一个元素设置为第一个房屋的金额dp[1] = Math.max(nums[0], nums[1]);  // 将dp的第二个元素设置为第一二个房屋中的金额较大者for (int i = 2; i < nums.length; i++) { // i=2代表从第3间屋子开始算起dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.length - 1];}
}

213. 打家劫舍 II

中等
提示
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

难点:要把环展开成线,无法判断从哪里选起就从头开始了,不能说因为是一个环就无法碰它了,总得有个破局点。偷东西是一家一家偷的,总得找第个一家先试试。归根到底,就是比打家劫舍多了一个限制条件:首尾不能同时偷。

思路:

在这里插入图片描述
在这里插入图片描述

class Solution {public int rob(int[] nums) {if (nums.length == 0) return 0; // 如果没有房屋,返回0if (nums.length == 1) return nums[0]; // 如果只有一个房屋,返回其金额int result1 = myRob(nums, 0, nums.length - 1); // 选首部屋子int result2 = myRob(nums, 1, nums.length);  // 选尾部屋子return Math.max(result1, result2);}public int myRob(int[] nums, int start, int end) {int pre = 0; // 前一位int prepre = 0; // 前前一位int temp = 0; // 用作交换for (int i = start; i < end; i++) {temp = pre;// 和二维相比,这里也做了dp[0] 和dp[1] 的初始化,当然,要把dp[0] 看作之前还有一位 0// 注意此时的pre已经是dp[i]了,// 可以看看原来的公式就明白了:dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);pre = Math.max(pre, prepre + nums[i]); prepre = temp;}return pre;}
}

337. 打家劫舍 III

中等
相关标签
相关企业
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。

除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。

思路:

使用爷爷、两个孩子、4 个孙子来说明问题
首先来定义这个问题的状态
爷爷节点获取到最大的偷取的钱数呢

首先要明确相邻的节点不能偷,也就是爷爷选择偷,儿子就不能偷了,但是孙子可以偷
二叉树只有左右两个孩子,一个爷爷最多 2 个儿子,4 个孙子

作者:房建斌学算法
链接:https://leetcode.cn/problems/house-robber-iii/solutions/47828/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
每个节点可选择偷或者不偷两种状态,根据题目意思,相连节点不能一起偷

当前节点选择偷时,那么两个孩子节点就不能选择偷了
当前节点选择不偷时,两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷,1 代表偷
任何一个节点能偷到的最大钱的状态可以定义为

当前节点选择不偷:当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
当前节点选择偷:当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
表示为公式如下

root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])
root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;

将公式做个变换就是代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int rob(TreeNode root) {int[] result = robAction(root);return Math.max(result[0], result[1]);}public int[] robAction(TreeNode root) {if (root == null) return new int[2]; // 如果该节点为空,那么偷或不偷它都返回0,所以它的result为[0, 0]int[] result = new int[2];// 后续遍历,因为要从底下找到上面int[] left = robAction(root.left); int[] right = robAction(root.right);// 当前节点选择不偷:当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱, 但是不是说左右孩子必须偷,所以是选它们偷或者不偷的最大值result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);// 当前节点选择偷:当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数result[1] = root.val + left[0] + right[0];return result;}
}

这篇关于day52 动态规划part9的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/850600

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

轨迹规划-B样条

B样条究竟是干啥的?白话就是给出一堆点,用样条的方式,给这些点连接起来,并保证丝滑的。 同时B样条分为准均匀和非均匀,以下为准均匀为例。 参考链接1:https://zhuanlan.zhihu.com/p/50626506https://zhuanlan.zhihu.com/p/50626506 参考链接2: https://zhuanlan.zhihu.com/p/536470972h

PMBOK® 第六版 规划进度管理

目录 读后感—PMBOK第六版 目录 规划进度管理主要关注为整个项目期间的进度管理提供指南和方向。以下是两个案例,展示了进度管理中的复杂性和潜在的冲突: 案例一:近期,一个长期合作的客户因政策要求,急需我们为多家医院升级一个小功能。在这个过程中出现了三个主要问题: 在双方确认接口协议后,客户私自修改接口并未通知我们,直到催进度时才发现这个问题关于UI设计的部分,后台开发人员未将其传递给

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划

vue2实践:el-table实现由用户自己控制行数的动态表格

需求 项目中需要提供一个动态表单,如图: 当我点击添加时,便添加一行;点击右边的删除时,便删除这一行。 至少要有一行数据,但是没有上限。 思路 这种每一行的数据固定,但是不定行数的,很容易想到使用el-table来实现,它可以循环读取:data所绑定的数组,来生成行数据,不同的是: 1、table里面的每一个cell,需要放置一个input来支持用户编辑。 2、最后一列放置两个b