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

C++动态规划经典试题解析之打家劫舍系列

1.前言

力扣上有几道与打家劫舍相关的题目,算是学习动态规划时常被提及的经典试题,很有代表性,常在因内大大小小的社区内看到众人对此类问题的讨论。

学习最好的方式便是归纳总结、借鉴消化,基于这个目的,本文对此类问题也做了讲解,在一些优秀思想的基础上添加了个人观点。

闲话少说,进入正文,开始打家劫舍,看今晚收获几何?

2. 线性盗贼

2.1 问题描述

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

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

示例1:
输入:[1,2,3,1]

输出:4

解释:偷窃 1号房屋(金额=1),然后偷窃3号房屋(金额=3)。偷窃到的最高金额=1+3=4

示例2:

输入:[2,7,9,3,1]

输出:12

解释:偷窃 1 号房屋(金额 = 2),偷 3 号房屋(金 = 9),接着偷 5 号房屋(金额 =1)偷窃到的最高金额=2+9+1=12。

2.2 问题分析

在打劫之前先不要急入进入房间,应该是先做全局的估算。

想象当盗贼从第一间房屋开始偷窃,他可以选择是偷还是不偷。偷还是不偷的选择不是源于他瞬时良心上的发现,而是收益的多少。如果只有一间房间,他会毫不犹豫的选择偷,这样才能带来今晚最大的收益。

下图所示为当只有一间房子时盗贼能获取到的最高金额。

27_0.png

如果有 2 间房屋,盗贼面对第一间房屋时会如何想呢?

收益固然重要,但是如果触发了报警系统,偷鸡不成蚀把米这样的赔本生意,肯定是不能做的。所以他的想法是可以偷,如果从此房间内的获取到的收益大于从另一个房间内获取到受益,否则,放弃当前房间,而选择进入第二间房间。

28.png

29.png

怎么知道偷还是不偷哪一个获取的收益最大。唯一法则就是比较,也就偷和不偷两者的受益取其大。如果只

相关文章:

C++动态规划经典试题解析之打家劫舍系列

1.前言 力扣上有几道与打家劫舍相关的题目,算是学习动态规划时常被提及的经典试题,很有代表性,常在因内大大小小的社区内看到众人对此类问题的讨论。 学习最好的方式便是归纳总结、借鉴消化,基于这个目的,本文对此类问题也做了讲解,在一些优秀思想的基础上添加了个人观…...

24届近5年东南大学自动化考研院校分析

今天给大家带来的是东南大学控制考研分析 满满干货~还不快快点赞收藏 一、东南大学 学校简介 东南大学是我国最早建立的高等学府之一,素有“学府圣地”和“东南学府第一流”之美誉。东南大学前身是创建于1902年的三江师范学堂。1921年经近代著名教育家…...

electron、electron-forge 安装

npm修改了registry,安装依旧无效 使用cnpm 倒是可以解决,但是 npx electron-forge import 中 Installing dependencies 使用的是npm 给出一次性解决方案: step1:切换npm的下载源,可以使用nrm 进行管理,有…...

go的strings用法

strings 是 Go 语言标准库中提供的一个包,用于处理字符串相关的操作。这个包包含了许多函数,可以用于字符串的切割、拼接、替换、查找等操作。下面是一些常用的 strings 包函数和用法示例: package mainimport ("fmt""string…...

echo用法、linxu课堂练习题、作业题

一、课堂练习 练习一: 4、普通用户修改密码: root修改密码: 5、修改主机名:hostnamectl hostname 主机名 查看:hostnamectl或者cat etc/hostname 练习二: 1、 mkdir /root/html touch /root/html/index.…...

WordPress使用【前端投稿】功能时为用户怎么添加插入文章标签

在使用Wordpress做前端投稿功能的时候,可能需要用户填写文章标签,在插入文章的时候很多人不知道怎么把这些标签插入进去,下面这篇文章来为大家带来WordPress使用前端投稿功能时插入文章标签方法。 在Wordpress里 wp_insert_post 此函数的作…...

第二章:CSS基础进阶-part1:CSS高级选择器

文章目录 一、 组合选择器二、属性选择器三、伪类选择器1、动态伪类选择器2、状态伪类选择器3、结构性伪类选择器4、否定伪类选择器 一、 组合选择器 后代选择器:E F子元素选择器: E>F相邻兄弟选择器:EF群组选择器:多个选择器…...

js 正则表达式 限制input元素内容必须以abc开头,123结尾

要通过正则表达式验证一个输入元素的内容是否以"abc"开头且以"123"结尾,您可以使用 ^ 表示开头,$ 表示结尾,以及适当的字符类或具体字符。以下是一个示例正则表达式: var regex /^abc.*123$/;上面的正则表达…...

Linux下安装nginx (tar解压版安装)

Linux下安装nginx (tar安装) 1、下载nginx 官方下载地址https://nginx.org/en/download.html 在这里插入图片描述 2.解压 解压‘nginx-1.16.1.tar.gz’到指定目录(/usr/local/myWorkSpace)并且重命名 命令: tar -xvf nginx-1.16.1.tar.gz …...

不同组件之间相互传递信息的方式(拓展知识)

文章目录 🐒个人主页🏅JavaEE系列专栏📖前言:🏨补充知识:不同组件之间通过get()方式传递信息 🎀父组件与子组件之间的信息交互 $emit 方法🏅父组件给子组件发…...

idea找不到DataBase

一、我想把数据库跟我的idea链接,结果发现找不到。如图。 二、解决方案 找到 file ---setting 找到plugin------找到marketplace 我的已经出现了...

研发工程师玩转Kubernetes——PVC使用Label和storage选择PV

在《研发工程师玩转Kubernetes——local型PV和PVC绑定过程中的状态变化》和《研发工程师玩转Kubernetes——使用local型PV在不同Pod上共享数据》中,我们介绍了指定VPC的spec.volumeName为PV名称来绑定它们的方法。本文将介绍PVC在创建时,系统自动选择绑定…...

【VUE】localStorage、indexedDB跨域数据操作实战笔记

由于业务需求&#xff0c;最近研究localStorage、indexedDB等如何跨域进行CRUD管理&#xff0c;经过一番研究&#xff0c;封装了如下代码并做个笔记 环境 vue: ^3.3.4 实战 发送端(即触发站点) 在App.vue中引入CrossDomainStorage组件(后面有实现过程) <script setup&g…...

四、web应用程序技术——HTTP

文章目录 1 HTTP请求2 HTTP响应3 HTTP方法4 URL5 HTTP消息头5.1 常用消息头5.2 请求消息头5.3 响应消息头 6 cookie7 状态码8 HTTP代理9 HTTP身份验证 HTTP&#xff08;HyperText Transfer Protocol&#xff0c;超文本传输协议&#xff09;是访问万维网使用的核心通信协议&…...

B2B2C小程序商城系统--跨境电商后台数据采集功能开发

搭建一个B2B2C小程序商城系统涉及到多个步骤和功能开发&#xff0c;其中包括跨境电商后台数据采集功能的开发。具体搭建步骤如下&#xff1a; 一、系统搭建 1. 确定需求和功能&#xff1a;根据B2B2C商城的需求&#xff0c;确定系统的功能和模块&#xff0c;包括商品管理、订单…...

Python-OpenCV中的图像处理-形态学转换

Python-OpenCV中的图像处理-形态学转换 形态学转换腐蚀膨胀开运算闭运算形态学梯度礼帽黑帽形态学操作之间的关系 形态学代码例程 形态学转换 形态学操作:腐蚀&#xff0c;膨胀&#xff0c;开运算&#xff0c;闭运算&#xff0c;形态学梯度&#xff0c;礼帽&#xff0c;黑帽等…...

理解 Python 的 for 循环

前言 嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 在本篇博客中&#xff0c;我们将讨论 Python 中 for 循环的原理。 我们将从一组基本例子和它的语法开始&#xff0c;还将讨论与 for 循环关联的 else 代码块的用处。 然后我们将介绍迭代对象、迭代器和迭代器协议&…...

携程验证码

今日话题&#xff1a;凑字数水文章。大表哥们感兴趣可以看看。 携程验证类型总共有3种。无感&#xff0c;滑块&#xff0c;点选。 process_type&#xff1a;None为无感 验证接口&#xff1a;https://ic.ctrip.com/captcha/v4/risk_inspect process_type&#xff1a;JIGSAW为…...

资深媒体人宋繁银加入《数据猿》任总编辑,全面负责公司整体内容工作

大数据产业创新服务媒体 ——聚焦数据 改变商业 2023年7月北京&#xff0c;《数据猿》宣布正式任命宋繁银为总编辑&#xff0c;全面负责公司整体内容工作。此次重要的人事任命标志着《数据猿》的发展迈上了一个新的台阶&#xff0c;对于《数据猿》团队而言&#xff0c;不仅是一…...

【Unity实战100例】人物状态栏UI数据刷新—MVC观察者模式

目录 一.创建Model层数据模型 二.创建View层关联UI组件 三.创建Controller层使得V和M数据关联 源码:htt...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...