动态规划之打家劫舍
大纲
- 题目
- 思路
- 第一步:确定下标含义
- 第二步:确定递推公式
- 第二步:dp数组如何初始化
- 第三步:确定遍历顺序
- 第四步:举例推导dp数组
- 总结
最近有人询问我 LeetCode 「打家劫舍」系列问题(英文版叫 House Robber)怎么做,上网调研后发现,这一系列题目的点赞非常之高,是比较有代表性和技巧性的动态规划题目,今天就来聊聊这道题目。
以下三道题目,可在看完本文后,练练手
打家劫舍 I
打家劫舍 II
打家劫舍 III
打家劫舍I就是其他衍生题的根,所以我就以打家劫舍I为例题讲解
题目
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 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 。
提示:
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 400
思路
对于初学者,而言,看过题之后,肯定会有一点朦胧。为什么呢(ο´・д・)??
初步分析以后,能看到,一间房屋是否偷取,取决于 上一间房屋与上两间房屋!
到此为止,就更能感受到一种纠缠的关系,不过通过这种关系,就能顺理成章的发现递推关系。所以这就涉及到了动态规划。
有一定基础的人都知道,动态规划算是一种公式题型,对应的就会出来一套公式
我比较佩服的一个博主Carl,他把动归总结成了五部曲,如下:
- 确定下标含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
第一步:确定下标含义
我们设一个dp数组,vector dp(nums.size(),0);
其中dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
第二步:确定递推公式
假设一下,现在处于第i个节点,
如果取上一个节点的情况下,因为本节点不能偷,故:dp[i]=dp[i-1];
如果不取上一个节点,那就能偷本节点,故有price[i]:dp[i]=dp[i-2]+nums[i];
综合而言,就得出来:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
第二步:dp数组如何初始化
从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出,递推公式的基础就是dp[0] 和 dp[1]
故:dp[0] 肯定时 dp[0] = nums[0]
而dp[1],为了取最大值 dp[1] = max(dp[0],dp[1]);
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
第三步:确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历
for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
第四步:举例推导dp数组
这里就不细讲喽,一般是在出错时,把dp数组打印出来,分析哪里错了。
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(),0);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);// 遍历方式for(int i=2; i<nums.size(); ++i){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.size()-1];}
};
总结
其他大打家劫舍,大多是本题的衍伸,这说明本题恰恰是一道经典题
虽然本题简单,但这就不重视了吗???
最后在此,送坚持到这里的读者一句话:
简单题,用来培养方法; 难题,用来突破自我; 两者结合,方能突破至高; 当难题,难得你受不了时,恰恰是因为你没有重视简单题!
希望大家有所收获。
相关文章:
动态规划之打家劫舍
大纲 题目思路第一步:确定下标含义第二步:确定递推公式第二步:dp数组如何初始化第三步:确定遍历顺序第四步:举例推导dp数组 总结 最近有人询问我 LeetCode 「打家劫舍」系列问题(英文版叫 House Robber&…...
嵌入式入门学习——8基于Protues仿真Arduino+SSD1306液晶显示数字时钟
0 系列文章入口 嵌入式入门学习——0快速入门,Let‘s Do It! SSD1306 1 Protues查找SSD1306器件并放置在画布,画好电气连接(这里VCC和GND画反了,后面仿真出错我才看见,要是现实硬件估计就烧毁了…...
盘点现代浏览器的各种神奇能力,功能令人惊讶
盘点现代浏览器的各种神奇能力,功能令人惊讶😮 浏览器的进化 一个运行在浏览器里面的操作系统。一个炫酷的量子纠缠网页。内嵌在浏览器里面的AI大模型。 随着web技术的迅猛发展,现代浏览器已经不仅仅是一个浏览网页的工具了。它的功能早已进…...
人工智能停滞:人工智能投资与人工智能采用之间的差距
关注公众号网络研究观获取更多内容。 人工智能继续影响着云战略,但人工智能的实施速度比大多数人预测的要慢。这让在人工智能上押下重注的技术提供商感到沮丧。到底发生了什么? Censuswide 代表 Red Hat 近期开展了一项调查,调查对象为英国…...
高效容器化技术(3)---docker镜像仓库
1.镜像仓库 Docker镜像仓库是存储和管理Docker镜像的地方。它允许用户上传、下载和共享Docker镜像,从而方便在不同的主机上部署和运行应用程序。 常见的Docker镜像仓库包括: Docker Hub:官方的Docker镜像仓库,包含了大量的公共镜…...
使用docker搭建lnmp运行WordPress
一,部署目的 使用 Docker 技术在单机上部署 LNMP 服务(Linux Nginx MySQL PHP)。部署并运行 WordPress 网站平台。掌握 Docker 容器间的互联及数据卷共享。 二,部署环境 操作系统:CentOS 7Docker 版本࿱…...
【设计模式】深入理解Python中的桥接模式(Bridge Pattern)
深入理解Python中的桥接模式(Bridge Pattern) 在软件开发中,我们常常会遇到一个类随着功能的扩展,继承层次越来越复杂,导致系统僵化,难以维护。桥接模式(Bridge Pattern)提供了一种…...
YOLOv11改进策略【卷积层】| SAConv 可切换的空洞卷积 二次创新C3k2
一、本文介绍 本文记录的是利用SAConv优化YOLOv11的目标检测网络模型。空洞卷积是一种在不增加参数量和计算量的情况下,通过在卷积核元素之间插入空洞来扩大滤波器视野的技术。并且为了使模型能够适应不同尺度的目标,本文利用SAConv将不同空洞率卷积结果进行结合,来获取更全…...
Javaweb基础-axios
Axios 是一个基于 Promise 的 HTTP 库,可以用在浏览器和 node.js 中。 GET方法 get请求第一种写法 //后端 Slf4j RestController RequestMapping("/demo") public class DemoController {RequestMapping("/getTest")// 被RequestParam标记的参数…...
智能EDA小白从0开始 —— DAY20 OrCAD
以下是对OrCAD和MATLAB两种EDA工具的深入解析,内容扩展至约2220字: OrCAD:电子设计自动化的强大工具 OrCAD,作为电子设计自动化(EDA)领域的佼佼者,为电子工程师们提供了一套全面的设计解决方案…...
C# WebApi 接口测试工具:WebApiTestClient应用技术详解
目录 一、引言 二、WebApiTestClient介绍 1、特性 2、应用场景 三、WebApiTestClient具体使用 1、WebApi项目引入组件 2、如何使用组件 1、修改Api.cshtml文件 2、配置读取注释的xml路径 3、测试接口 四、总结 一、引言 由于最近项目需要开发WebApi接口&…...
Qt_ymode自己实现
文章内容: 通过Qt实现Ymode协议的封装。通过传入的数据从里面一包一包拿数据。可以用作平时串口和网口的通信。也可以用来程序升级。 #include "ymodem.h"Ymodem::Ymodem() {m_data = nullptr; }Ymodem...
5.3章节python中字典:字典创建、元素访问、相关操作
1.字典的创建和删除 2.字典的访问和遍历 3.字典的相关操作 4.字典的生成式 一、字典的创建和删除 字典(dictionary)是一种用于存储键值对(key-value pairs)的数据结构。每个键(key)都映射到一个值…...
ECCV2024 Tracking 汇总
一、OneTrack: Demystifying the Conflict Between Detection and Tracking in End-to-End 3D Trackers paper: https://www.ecva.net/papers/eccv_2024/papers_ECCV/papers/01174.pdf 二、VETRA: A Dataset for Vehicle Tracking in Aerial Imagery paper&#…...
C语言知识点
命名规则: 字符组成:标识符只能由字母(A~Z,a~z)、数字(0~9)和下划线(_)组成。首字符要求:标识符的第一个字符必须是字母或下划线,不能是数字。长…...
ICMP协议以及ARP欺骗攻击
ping 命令使用的是 ICMP(Internet Control Message Protocol)协议,而不是 TCP 或 UDP 协议。因此,ping 命令并不使用特定的端口号。 ICMP 协议 ICMP 是一种网络层协议,主要用于在 IP 网络中传递控制消息。ping 命令利…...
qt5.12.12插件机制无法加载插件问题
环境:win11 vs2015 qt5.12.12 问题描述:确保插件代码正确的情况下,无法解析插件接口(即QPluginLoader类的instance(); 返回为空)。 问题现象:1、qt5.12.12的debug下无法解析;2、release下禁…...
机器学习面试笔试知识点-线性回归、逻辑回归(Logistics Regression)和支持向量机(SVM)
机器学习面试笔试知识点-线性回归、逻辑回归Logistics Regression和支持向量机SVM 一、线性回归1.线性回归的假设函数2.线性回归的损失函数(Loss Function)两者区别3.简述岭回归与Lasso回归以及使用场景4.什么场景下用L1、L2正则化5.什么是ElasticNet回归6.ElasticNet回归的使…...
SpringBoot民宿预订系统设计与实现
2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统,它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等,非常…...
linux环境下C程序的编译过程以及makefile的简单使用
在windows下,很多用来进行编程软件对于写好的文件,点击编译即可生成想要文件。如.exe可执行文件,.hex文件或者.bin文件等等。软件为我们省略了很多事。但是对于linux初学者来说,初次接触linux系统,面对命令行黑框框有点…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
