当资深程序员深夜去“打劫”会发生什么?——打家劫舍详解
文章目录
- 一、前言
- 二、概述
- 三、打家劫舍第一晚
- 四、打家劫舍第二晚
- 五、打家劫舍第三晚......
一、前言
大家好久不见,正如标题所示,今天我不打算聊一些枯燥的算法理论,我们来聊一聊程序员有多厉害!
注意!!!:本文诣在讲解
动态规划
里的打家劫舍问题,无任何不良导向!!!
二、概述
一个月黑风高的夜晚~,你回到了村庄,你是一名资深的程序员,你工作认真努力,但苦于老板压迫,生活常常捉襟见肘,于是你的内心萌生了罪恶的想法!你准备在这个村庄里打劫!
三、打家劫舍第一晚
第一天晚上,你来到了一个村庄,你计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的 唯一制约因素
就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。而你想要在一夜之内偷取最高金额。
聪明的你知道如果报警器响起会发生什么,所以你打算运用你作为程序员的聪明才智来帮助你完成打劫!
于是你简单分析了街道房屋的构成,并将其抽象为了数组,简单分析报警器就可以知道,只要不偷相邻元素的钱就不会触发报警!
看过前两期动态规划的你,立马就意识到这是一个动态规划问题,没看过也没关心,你稍微动了一下脑筋,梳理出来以下思路:
✔️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);//选择最大的那个啦!!!}
};
五、打家劫舍第三晚…
鉴于你前两晚作案都非常顺利,不出所料,第三天晚上你再次来到了一个村庄,这次村庄结构竟然变成了二叉树!!作为程序员的你马上就兴奋了起来,那么你到底能不能顺利偷得第三个村庄,拿到最多钱呢。
欲知后事如何,且听下节课分解!!!大家可以先自己想一想,下次我们先学会二叉树的基本知识,再来偷最后的村子!
如果你感觉本篇文章对你有所帮助,可以点赞 + 收藏 +关注 支持一下学者哦~ 我们下次再见~
相关文章:

当资深程序员深夜去“打劫”会发生什么?——打家劫舍详解
文章目录一、前言二、概述三、打家劫舍第一晚四、打家劫舍第二晚五、打家劫舍第三晚......一、前言 大家好久不见,正如标题所示,今天我不打算聊一些枯燥的算法理论,我们来聊一聊程序员有多厉害! 注意!!&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的安装相对简单,下载安装包安装(安装包node-v19.6.0-x64.msi), nodejs 安装 然后一路狂点下一步就可以了 安装完成后,在终端中输入node -v,显示版本号则表示安装成功 node-v16.13.1 1.2 JDK安装及环境变…...

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

Vue3 如何实现一个函数式右键菜单(ContextMenus)
前言: 最近在公司 PC 端的项目中使用到了右键出现菜单选项这样的一个工作需求,并且自己现在也在实现一个偶然迸发的 idea( 想用前端实现一个 windows 系统从开机到桌面的 UI),其中也要用到右键弹出菜单这样的一个功能,…...

ffmpeg转码转封装小工具开发
如下图所示,是本人开发的一个转码转封装小工具 其中目标文件视频编码格式支持:H264,H265,VP8,VP9。 目标文件封装格式支持:mp4,mkv,avi,mov,flv。 目标文件音频编码格式支持两个,COPY和AAC&am…...
重入和线程安全
在整个文档中,重入和线程安全用于标记类和函数,从而表明怎样在多线程应用中使用它们。 线程安全函数可以从多个线程同时调用,即使调用使用共享数据也是如此,因为对共享数据的所有引用都是序列化的。也可以从多个线程同时调用重入…...

MySQL数据库06——条件查询(WHERE)
MySQL条件查询,主要是对数据库里面的数据按照一定条件进行筛选,主要依靠的是WHERE语句进行。 先来了解一下基础的条件运算。 关系运算符 逻辑运算符 逻辑运算符优先级:NOT>AND>OR,关系运算符>逻辑运算符 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小程序端 小程序登录页面,用户也可以在此页面进行注册并且登录等。 登录成功后可以在我的个人中心查看自己的个人信息或者修改信息等 在广播信息中我们可以查看校运会发布的一些信息情况。 在首页我们可以看到校运会具体有什么项目运动。 在查看具体有什么活动我…...

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

SpringBoot+Vue实现师生健康信息管理系统
文末获取源码 开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7/8.0 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包:Maven3.3.9 浏…...
数据库第四章节第三次作业内容
1、显示所有职工的基本信息。 2、查询所有职工所属部门的部门号,不显示重复的部门号。 3、求出所有职工的人数。 4、列出最高工和最低工资。 5、列出职工的平均工资和总工资。 6、创建一个只有职工号、姓名和参加工作的新表,名为工作日期表…...

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

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

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

数据类型与运算符
1.字符型作用: 字符型变量用于显示单个字符语法: char cc a ;注意1: 在显示字符型变量时,用单引号将字符括起来,不要用双引号注意2: 单引号内只能有一个字符,不可以是字符串C和C中字符型变量只占用1个字节。字符型变是并不是把字符本身放到内存中存储&am…...
算法刷题-二叉树的锯齿形层序遍历、用栈实现队列 栈设计、买卖股票的最佳时机 IV
文章目录二叉树的锯齿形层序遍历(树、广度优先搜索)用栈实现队列(栈、设计)买卖股票的最佳时机 IV(数组、动态规划)二叉树的锯齿形层序遍历(树、广度优先搜索) 给定一个二叉树&…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...

P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...