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

当资深程序员深夜去“打劫”会发生什么?——打家劫舍详解

文章目录

  • 一、前言
  • 二、概述
  • 三、打家劫舍第一晚
  • 四、打家劫舍第二晚
  • 五、打家劫舍第三晚......

一、前言

大家好久不见,正如标题所示,今天我不打算聊一些枯燥的算法理论,我们来聊一聊程序员有多厉害!

注意!!!:本文诣在讲解动态规划里的打家劫舍问题,无任何不良导向!!!

二、概述

一个月黑风高的夜晚~,你回到了村庄,你是一名资深的程序员,你工作认真努力,但苦于老板压迫,生活常常捉襟见肘,于是你的内心萌生了罪恶的想法!你准备在这个村庄里打劫!

三、打家劫舍第一晚

第一天晚上,你来到了一个村庄,你计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的 唯一制约因素 就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。而你想要在一夜之内偷取最高金额。
在这里插入图片描述

聪明的你知道如果报警器响起会发生什么,所以你打算运用你作为程序员的聪明才智来帮助你完成打劫!

于是你简单分析了街道房屋的构成,并将其抽象为了数组,简单分析报警器就可以知道,只要不偷相邻元素的钱就不会触发报警!

在这里插入图片描述
看过前两期动态规划的你,立马就意识到这是一个动态规划问题,没看过也没关心,你稍微动了一下脑筋,梳理出来以下思路:

✔️dp数组
在第0间~第 i 间房子内,要遵守相邻房间不能偷的原则,偷得最大金额!这个i是会变化的,所以你决定使用一个dp数组来保存你能偷的最大金额

dp[i] 表示: 第0间房子~第i间房子内按照规则能偷取的最大金额

✔️状态转移
片刻后,你决定要偷一共i间房子的钱,并打听好了每间房子有多少钱可以偷(value)。

于是你想,若要求dp[i],无非就两种情况:

1. 偷第i家

2.不偷第i家

1.那如果偷第i家,根据规则,相邻房间不能再偷,所以第i-1家就要避开

  • dp[i] = dp[i-2] + value[i]

2.那如果不偷第i家,根据规则,i-1家就不需要避开

  • dp[i] = dp[i-1];

而我们只需要在上述两种情况下选金额较大的即是dp[i]的值!因此状态转移方程即为:

dp[i] = max(dp[i-1],dp[i-2] + value[i]);

到这里,你不禁感叹不愧是程序员,轻松做到了其他人做不到的事情!

✔️初始化
推导出上述动态转移方程,你就自然而然想到前两个元素要初始化,那初始化为什么好呢,回顾了一下dp数组的含义,你顺利完成了初始化

  • dp[0] = value[0];
  • dp[1] = max(value[0],value[1]);

简单解释一下:

你只有一间房子可选,你就说你选不选吧~
不能都选,但总得选个贵的吧~

✨参考代码

class Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 0) return 0;if(nums.size() == 1) return nums[0];vector<int> dp(nums.size());dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);for(int i = 2;i<nums.size();i++){dp[i] = max(dp[i-2]+nums[i],dp[i-1]);}return dp[nums.size()-1];}
};

四、打家劫舍第二晚

昨晚你作案非常顺利,成功拿到了最大金额,为了避免被别人发现,第二天你来到了一个新的村庄,村庄结构变成了一个环形!,你同样不能偷相邻房间的钱!!

在这里插入图片描述
你分析了一下,发现这个村庄的构成与上个村庄非常相似,只是首尾相连了而已,那这样的变化会带来什么问题呢?

很简单,无非就是选择了第一家就不能偷最后一家,选择了最后一家,就一定不能偷第一家。

在这里插入图片描述这样,你成功将一个环形结构拆成了两个队列结构,只要分别求出他们,选择最大的那个即可!

那分别求每一个队列的过程,和你第一天的情况完全一致,你也很轻松的偷到了最多的钱。

class Solution {
public://抽象第一天的过程int robRange(vector<int>& nums,int start,int end){if (end == start) return nums[start];vector<int> dp(nums.size());dp[start] = nums[start];dp[start+1] = max(nums[start],nums[start+1]);for(int i = start+2;i<=end;i++){dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];}int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); // 第一个队列int result2 = robRange(nums, 1, nums.size() - 1); //第二个队列return max(result1, result2);//选择最大的那个啦!!!}
};

五、打家劫舍第三晚…

鉴于你前两晚作案都非常顺利,不出所料,第三天晚上你再次来到了一个村庄,这次村庄结构竟然变成了二叉树!!作为程序员的你马上就兴奋了起来,那么你到底能不能顺利偷得第三个村庄,拿到最多钱呢。

在这里插入图片描述

欲知后事如何,且听下节课分解!!!大家可以先自己想一想,下次我们先学会二叉树的基本知识,再来偷最后的村子!

如果你感觉本篇文章对你有所帮助,可以点赞 + 收藏 +关注 支持一下学者哦~ 我们下次再见~

相关文章:

当资深程序员深夜去“打劫”会发生什么?——打家劫舍详解

文章目录一、前言二、概述三、打家劫舍第一晚四、打家劫舍第二晚五、打家劫舍第三晚......一、前言 大家好久不见&#xff0c;正如标题所示&#xff0c;今天我不打算聊一些枯燥的算法理论&#xff0c;我们来聊一聊程序员有多厉害&#xff01; 注意&#xff01;&#xff01;&am…...

linux 线程

文章目录1、线程的概念1.1、进程 vs 线程1.2、线程的种类2、线程的控制2.1、线程的创建2.2、线程的退出2.3、线程的取消2.4、线程的等待2.5、线程的分离2.5、线程清理函数线程清理函数响应的时机线程清理函数不响应的时机3、线程的同步和互斥3.1、锁机制3.1.1、锁的类型3.1.2、…...

Windows 安装appium环境

1 windows Appium环境 1.1 安装Node.js Node.js的安装相对简单,下载安装包安装&#xff08;安装包node-v19.6.0-x64.msi&#xff09;, nodejs 安装 然后一路狂点下一步就可以了 安装完成后,在终端中输入node -v,显示版本号则表示安装成功 node-v16.13.1 1.2 JDK安装及环境变…...

为什么要在电子产品中使用光耦合器?

介绍 光耦合器不仅可以保护敏感电路&#xff0c;还可以使工程师设计各种硬件应用。光耦合器通过保护元件&#xff0c;可以避免更换元件的大量成本。然而&#xff0c;光耦合器比保险丝更复杂。光耦合器还可以通过光耦合器连接和断开两个电路&#xff0c;从而方便地控制两个电路…...

Vue3 如何实现一个函数式右键菜单(ContextMenus)

前言: 最近在公司 PC 端的项目中使用到了右键出现菜单选项这样的一个工作需求&#xff0c;并且自己现在也在实现一个偶然迸发的 idea&#xff08; 想用前端实现一个 windows 系统从开机到桌面的 UI&#xff09;&#xff0c;其中也要用到右键弹出菜单这样的一个功能&#xff0c;…...

ffmpeg转码转封装小工具开发

如下图所示&#xff0c;是本人开发的一个转码转封装小工具 其中目标文件视频编码格式支持&#xff1a;H264&#xff0c;H265&#xff0c;VP8&#xff0c;VP9。 目标文件封装格式支持&#xff1a;mp4,mkv,avi,mov,flv。 目标文件音频编码格式支持两个&#xff0c;COPY和AAC&am…...

重入和线程安全

在整个文档中&#xff0c;重入和线程安全用于标记类和函数&#xff0c;从而表明怎样在多线程应用中使用它们。 线程安全函数可以从多个线程同时调用&#xff0c;即使调用使用共享数据也是如此&#xff0c;因为对共享数据的所有引用都是序列化的。也可以从多个线程同时调用重入…...

MySQL数据库06——条件查询(WHERE)

MySQL条件查询&#xff0c;主要是对数据库里面的数据按照一定条件进行筛选&#xff0c;主要依靠的是WHERE语句进行。 先来了解一下基础的条件运算。 关系运算符 逻辑运算符 逻辑运算符优先级&#xff1a;NOT>AND>OR&#xff0c;关系运算符>逻辑运算符 SQL特殊运算符…...

Lesson 6.5 机器学习调参基础理论与网格搜索

文章目录一、机器学习调参理论基础1. 机器学习调参目标及基本方法2. 基于网格搜索的超参数的调整方法2.1 参数空间2.2 交叉验证与评估指标二、基于 Scikit-Learn 的网格搜索调参1. sklearn 中网格搜索的基本说明2. sklearn 中 GridSearchCV 的参数解释3. sklearn 中 GridSearch…...

leetcode: Two Sum

leetcode: Two Sum1. 题目1.1 题目描述2. 解答2.1 baseline2.2 基于baseline的思考2.3 优化思路的实施2.3.1 C中的hashmap2.3.2 实施2.3.3 再思考2.3.4 最终实施3. 总结1. 题目 1.1 题目描述 Given an array of integers nums and an integer target, return indices of the …...

共享模型之无锁(三)

1.原子累加器 示例代码: public class TestAtomicAdder {public static void main(String[] args) {for (int i 0; i < 5; i) {demo(() -> new AtomicLong(0),(adder) -> adder.getAndIncrement());}for (int i 0; i < 5; i) {demo(() -> new LongAdder(),(…...

微信小程序 Springboot校运会高校运动会管理系统

3.1小程序端 小程序登录页面&#xff0c;用户也可以在此页面进行注册并且登录等。 登录成功后可以在我的个人中心查看自己的个人信息或者修改信息等 在广播信息中我们可以查看校运会发布的一些信息情况。 在首页我们可以看到校运会具体有什么项目运动。 在查看具体有什么活动我…...

走进独自开,带你轻松干副业

今天给大家分享一个开发者的福利平台——独自开&#xff08;点击直接注册&#xff09;&#xff0c;让你在家就能解决收入问题。 文章目录一、平台介绍二、系统案例三、获取收益四、使用平台1、用户注册2、用户认证3、任务报价五、文末总结一、平台介绍 简单说明 独自开信息科技…...

SpringBoot+Vue实现师生健康信息管理系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7/8.0 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.3.9 浏…...

数据库第四章节第三次作业内容

1、显示所有职工的基本信息。 2、查询所有职工所属部门的部门号&#xff0c;不显示重复的部门号。 3、求出所有职工的人数。 4、列出最高工和最低工资。 5、列出职工的平均工资和总工资。 6、创建一个只有职工号、姓名和参加工作的新表&#xff0c;名为工作日期表…...

一篇五分生信临床模型预测文章代码复现——FIgure 9.列线图构建,ROC分析,DCA分析 (四)

之前讲过临床模型预测的专栏,但那只是基础版本,下面我们以自噬相关基因为例子,模仿一篇五分文章,将图和代码复现出来,学会本专栏课程,可以具备发一篇五分左右文章的水平: 本专栏目录如下: Figure 1:差异表达基因及预后基因筛选(图片仅供参考) Figure 2. 生存分析,…...

神经网络实战--使用迁移学习完成猫狗分类

前言&#xff1a; Hello大家好&#xff0c;我是Dream。 今天来学习一下如何使用基于tensorflow和keras的迁移学习完成猫狗分类&#xff0c;欢迎大家一起前来探讨学习~ 本文目录&#xff1a;一、加载数据集1.调用库函数2.加载数据集3.数据集管理二、猫狗数据集介绍1.猫狗数据集介…...

Attention机制 学习笔记

学习自https://easyai.tech/ai-definition/attention/ Attention本质 Attention&#xff08;注意力&#xff09;机制如果浅层的理解&#xff0c;跟他的名字非常匹配。他的核心逻辑就是“从关注全部到关注重点”。 比如我们人在看图片时&#xff0c;对图片的不同地方的注意力…...

数据类型与运算符

1.字符型作用: 字符型变量用于显示单个字符语法: char cc a ;注意1: 在显示字符型变量时&#xff0c;用单引号将字符括起来,不要用双引号注意2: 单引号内只能有一个字符&#xff0c;不可以是字符串C和C中字符型变量只占用1个字节。字符型变是并不是把字符本身放到内存中存储&am…...

算法刷题-二叉树的锯齿形层序遍历、用栈实现队列 栈设计、买卖股票的最佳时机 IV

文章目录二叉树的锯齿形层序遍历&#xff08;树、广度优先搜索&#xff09;用栈实现队列&#xff08;栈、设计&#xff09;买卖股票的最佳时机 IV&#xff08;数组、动态规划&#xff09;二叉树的锯齿形层序遍历&#xff08;树、广度优先搜索&#xff09; 给定一个二叉树&…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...