LCR 090. 打家劫舍 II(leetcode)动态规划
文章目录
- 前言
- 一、题目分析
- 二、算法原理
- 1.状态表示
- 2.状态转移方程
- 3.初始化
- 4.填表顺序
- 5.返回值是什么
- 三、代码实现
- 总结
前言
在本文章中,我们将要详细介绍一下LeetcodeLCR 090. 打家劫舍 II。采用动态规划解决,这是一道经典的多状态dp问题
一、题目分析

计算小偷能偷到的最大金额数,并且题目规定:
🥉.两个相邻的房屋不能被偷
🥉.第一个房屋和最后一个房屋不能被偷
规定1比较好解决,对于规定2,我们采用分情况讨论的方法解决
🍔.第一个房间偷,第二个房间和最后一个不被偷,在(2,n-2)下标之间寻找最大金额,再加上nums[0].
🍔.第一个房间不被偷,最后一个房间不确定,在(1,n-1)下标之间寻找最大金额
🍔.二者取最大值,就是题目所返回的值
二、算法原理
1.状态表示
列出dp表,dp表中值的含义是什么
这可以细分为两个表,因为经过该房间时不确定偷与不偷
⭐️ .f[i]表示到达i房间时,资金被偷
⭐️.g[i]表示到达i房间时,资金没有被偷
2.状态转移方程
根据最近一步划分问题
🌟 f[i]:i位置被偷,那么根据题目规定,i-1位置就不能被偷,这不就正好是g[i-1],再加上i位置被偷的资金;
🌟g[i]:i位置没有被偷,i-1位置我们不确定有没有被偷,所以需要分为两种情况,这两种情况取最大值
🐧.i-1位置也没有被偷,就是g[i-1]
🐧.i-1位置被偷了,就是f[i-1]
结论:
f[i]=g[i-1]+nums[i];
g[i]=max(g[i-1],f[i-1])
3.初始化
保证填表不越界
f[1]需要g[0]的值;g[1]需要g[0]和f[0]的值, 所以需要初始化g[0]和f[0].
不用开辟额外的空间,这道题目的初始化很简单。
注意:数组的下标和边界条件
4.填表顺序
两个表一起填,从左往右
5.返回值是什么
max(f[n-1],g[n-1]);
三、代码实现
class Solution {
public:int massage(vector<int>& nums,int left,int right) {if(left>right){return 0;}//建表int n=nums.size();int f[n];int g[n];//初始化for(int i=0;i<n;i++){f[i]=g[i]=0;}f[left]=nums[left];g[0]=0;//填表for(int i=left;i<=right;i++){f[i]=g[i-1]+nums[i];g[i]=max(g[i-1],f[i-1]);}//返回值return max(f[right],g[right]);}int rob(vector<int>& nums) {int n=nums.size();//下标int ret1=massage(nums,2,n-2)+nums[0];int ret2=massage(nums,1,n-1);return max(ret1,ret2);}
};
总结
以上就是我们对LeetcodeLCR 090. 打家劫舍 II(leetcode)详细介绍,希望对大家的学习有所帮助,仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~
相关文章:
LCR 090. 打家劫舍 II(leetcode)动态规划
文章目录 前言一、题目分析二、算法原理1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值是什么 三、代码实现总结 前言 在本文章中,我们将要详细介绍一下LeetcodeLCR 090. 打家劫舍 II。采用动态规划解决,这是一道经典的多状态dp问题 一、题目分析…...
【小沐学Python】Python实现语音识别(Whisper)
文章目录 1、简介1.1 whisper简介1.2 whisper模型 2、安装2.1 whisper2.2 pytorch2.3 ffmpeg 3、测试3.1 命令测试3.2 代码测试:识别声音文件3.3 代码测试:实时录音识别 结语 1、简介 https://github.com/openai/whisper 1.1 whisper简介 Whisper 是…...
Nginx负载均衡实战
🎵负载均衡组件 ngx_http_upstream_module https://nginx.org/en/docs/http/ngx_http_upstream_module.html upstream模块允许Nginx定义一组或多组节点服务器组,使用时可以通过多种方式去定义服务器组 样例: upstream backend {server back…...
Redis skiplist源码解析(支持范围查询)
跳表是一个多层的有序链表,在跳表中进行查询操作时,查询代码可以从最高层开始查询。层数越高,结点数越少,同时高层结点的跨度会比较大。因此,在高层查询结点时,查询一个结点可能就已经查到了链表的中间位置…...
MVSNeRF:多视图立体视觉的快速推广辐射场重建(2021年)
MVSNeRF:多视图立体视觉的快速推广辐射场重建(2021年) 摘要1 引言2 相关工作3 MVSNeRF实现方法3.1 构建代价体3.2 辐射场的重建3.3 体渲染和端到端训练 3.4 优化神经编码体 Anpei Chen and Zexiang Xu and Fuqiang Zhao et al. MVSNeRF: Fast…...
华为OD机试真题-CPU算力分配-2023年OD统一考试(C卷)
题目描述: 现有两组服务器A和B,每组有多个算力不同的CPU,其中A[i]是A组第i个CPU的运算能力,B[i]是B组第i个CPU的运算能力。一组服务器的总算力是各CPU的算力之和。为了让两组服务器的算力相等,允许从每组各选出一个CPU进行一次交换,求两组服务器中,用于交换的CPU的算力,…...
校验数据是否重叠(各种操作符>,<,>=,<=,or,and)
最近接到一个需求,其中部分功能涉及到数据的重叠校验,并且录入的数据需要包含各种操作符。如果只通过java代码来查询并进行循环判断的话,判断情况会很复杂,幸好有同事的帮忙提供了一个用sql查询重叠部分的方法,现在分享…...
大一C语言作业 12.8
1.C 对一维数组初始化时,如果全部元素都赋了初值,可以省略数组长度。 这里没有指定数组长度,编译器会根据初始化列表的元素个数来确定数组长度。 2.C 在C语言中,字符数组是不能用赋值运算符直接赋值的。 3.C 在二维数组a中&#x…...
ELasticsearch:什么是语义搜索?
语义搜索定义 语义搜索是一种解释单词和短语含义的搜索引擎技术。 语义搜索的结果将返回与查询含义匹配的内容,而不是与查询中的单词字面匹配的内容。 语义搜索是一组搜索引擎功能,其中包括根据搜索者的意图及其搜索上下文理解单词。 此类搜索旨在通过…...
ooTD I 女儿是自己的,尽情打扮尽情可爱
分享女宝的时尚穿搭 奶乎乎的黄色也太好看了 超足充绒量+优质面料 柔软蓬松上身体验感超赞 怎么穿都好看系列 轻轻松松打造时尚造型!!...
第62天:django学习(十一)
cookie和session 发展史 一开始,只有一个页面,没有登录功能,大家看到东西都一样。 时代发展,出现了需要登录注册的网站,要有一门技术存储我们的登录信息,于是cookie诞生了。 cookie: - 存储形式:k:v键值对…...
Rust测试字符串的移动,Move
代码创建了一个结构体,结构体有test1 字符串,还有指向字符串的指针。一共创建了两个。 然后我们使用swap 函数 交换两个结构体内存的内容。 最后如上图。相同的地址,变成了另外结构体的内容。注意看指针部分,还是指向原来的地址…...
vue+electron问题汇总
1. Vue_Bug Failed to fetch extension, trying 4 more times 描述:项目启动时报错 解决:注释图片中内容 2. Module not found: Error: Can’t resolve ‘fs’ in 描述:项目启动报错 解决:vue.config.js中添加图中数据 3.导入…...
Linux中的网络时间服务器
本章主要介绍网络时间的服务器 使用chrony配置时间服务器配置chrony客户端服务器同步时间 1.1 时间同步的重要性 一些服务对时间要求非常严格,例如如图所示的由三台服务器搭建的ceph集群 这三台服务器的时间必须保持一致,如果不一致,就会显…...
fastadmin打印页面
如下图选中订单号进行打印 html中增加代码 <div id"toolbar" class"toolbar"><a href"javascript:;" class"btn btn-primary btn-refresh" title"{:__(Refresh)}" ><i class"fa fa-refresh">&l…...
Java 将word转为PDF的三种方式和处理在服务器上下载后乱码的格式
我这边是因为业务需要将之前导出的word文档转换为PDF文件,然后页面预览下载这样的情况。之前导出word文档又不是我做的,所以为了不影响业务,只是将最后在输出流时转换成了PDF,当时本地调用没什么问题,一切正常…...
C\C++ 获取最值
C C 语言的不同类型的最值可以在 limits.h 头文件里找到定义 #include <limits.h>int main() {printf("%d", INT_MAX); // 整数最大值printf("%d", INT_MIN); // 整数最小值 } C C 有模板,可以通过替换下面的 int 和 doubleÿ…...
机器学习之无监督学习:九大聚类算法
今天,和大家分享一下机器学习之无监督学习中的常见的聚类方法。 今天,和大家分享一下机器学习之无监督学习中的常见的聚类方法。 在无监督学习中,我们的数据并不带有任何标签,因此在无监督学习中要做的就是将这一系列无标签的数…...
Linux高级管理-搭建网站服务
在Ihternet 网络环境中,Web 服务无疑是最为流行的应用系统。有了Web站点,企业可以充分 展示自己的产品,宣传企业形象。Web站点还为企业提供了与客户交流、电子商务交易平台等丰富 的网络应用。部署与维护Web 服务是运维工程师必须掌握的一个技…...
Windows 系统,TortoiseSVN 无法修改 Log 信息解决方法
使用SVN提交版本信息时,注释内容写的不全。通过右键TortoiseSVN的Show log看到提交的的注释,右键看到Edit log message的选项,然而提交后却给出错误提示: Repository has not been enabled to accept revision propchanges; ask …...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
