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

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.返回值是什么 三、代码实现总结 前言 在本文章中&#xff0c;我们将要详细介绍一下LeetcodeLCR 090. 打家劫舍 II。采用动态规划解决&#xff0c;这是一道经典的多状态dp问题 一、题目分析…...

【小沐学Python】Python实现语音识别(Whisper)

文章目录 1、简介1.1 whisper简介1.2 whisper模型 2、安装2.1 whisper2.2 pytorch2.3 ffmpeg 3、测试3.1 命令测试3.2 代码测试&#xff1a;识别声音文件3.3 代码测试&#xff1a;实时录音识别 结语 1、简介 https://github.com/openai/whisper 1.1 whisper简介 Whisper 是…...

Nginx负载均衡实战

&#x1f3b5;负载均衡组件 ngx_http_upstream_module https://nginx.org/en/docs/http/ngx_http_upstream_module.html upstream模块允许Nginx定义一组或多组节点服务器组&#xff0c;使用时可以通过多种方式去定义服务器组 样例&#xff1a; upstream backend {server back…...

Redis skiplist源码解析(支持范围查询)

跳表是一个多层的有序链表&#xff0c;在跳表中进行查询操作时&#xff0c;查询代码可以从最高层开始查询。层数越高&#xff0c;结点数越少&#xff0c;同时高层结点的跨度会比较大。因此&#xff0c;在高层查询结点时&#xff0c;查询一个结点可能就已经查到了链表的中间位置…...

MVSNeRF:多视图立体视觉的快速推广辐射场重建(2021年)

MVSNeRF&#xff1a;多视图立体视觉的快速推广辐射场重建&#xff08;2021年&#xff09; 摘要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)

最近接到一个需求&#xff0c;其中部分功能涉及到数据的重叠校验&#xff0c;并且录入的数据需要包含各种操作符。如果只通过java代码来查询并进行循环判断的话&#xff0c;判断情况会很复杂&#xff0c;幸好有同事的帮忙提供了一个用sql查询重叠部分的方法&#xff0c;现在分享…...

大一C语言作业 12.8

1.C 对一维数组初始化时&#xff0c;如果全部元素都赋了初值&#xff0c;可以省略数组长度。 这里没有指定数组长度&#xff0c;编译器会根据初始化列表的元素个数来确定数组长度。 2.C 在C语言中&#xff0c;字符数组是不能用赋值运算符直接赋值的。 3.C 在二维数组a中&#x…...

ELasticsearch:什么是语义搜索?

语义搜索定义 语义搜索是一种解释单词和短语含义的搜索引擎技术。 语义搜索的结果将返回与查询含义匹配的内容&#xff0c;而不是与查询中的单词字面匹配的内容。 语义搜索是一组搜索引擎功能&#xff0c;其中包括根据搜索者的意图及其搜索上下文理解单词。 此类搜索旨在通过…...

ooTD I 女儿是自己的,尽情打扮尽情可爱

分享女宝的时尚穿搭 奶乎乎的黄色也太好看了 超足充绒量&#xff0b;优质面料 柔软蓬松上身体验感超赞 怎么穿都好看系列 轻轻松松打造时尚造型&#xff01;&#xff01;...

第62天:django学习(十一)

cookie和session 发展史 一开始,只有一个页面&#xff0c;没有登录功能&#xff0c;大家看到东西都一样。 时代发展&#xff0c;出现了需要登录注册的网站&#xff0c;要有一门技术存储我们的登录信息&#xff0c;于是cookie诞生了。 cookie: - 存储形式&#xff1a;k:v键值对…...

Rust测试字符串的移动,Move

代码创建了一个结构体&#xff0c;结构体有test1 字符串&#xff0c;还有指向字符串的指针。一共创建了两个。 然后我们使用swap 函数 交换两个结构体内存的内容。 最后如上图。相同的地址&#xff0c;变成了另外结构体的内容。注意看指针部分&#xff0c;还是指向原来的地址…...

vue+electron问题汇总

1. Vue_Bug Failed to fetch extension, trying 4 more times 描述&#xff1a;项目启动时报错 解决&#xff1a;注释图片中内容 2. Module not found: Error: Can’t resolve ‘fs’ in 描述&#xff1a;项目启动报错 解决&#xff1a;vue.config.js中添加图中数据 3.导入…...

Linux中的网络时间服务器

本章主要介绍网络时间的服务器 使用chrony配置时间服务器配置chrony客户端服务器同步时间 1.1 时间同步的重要性 一些服务对时间要求非常严格&#xff0c;例如如图所示的由三台服务器搭建的ceph集群 这三台服务器的时间必须保持一致&#xff0c;如果不一致&#xff0c;就会显…...

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文件&#xff0c;然后页面预览下载这样的情况。之前导出word文档又不是我做的&#xff0c;所以为了不影响业务&#xff0c;只是将最后在输出流时转换成了PDF&#xff0c;当时本地调用没什么问题&#xff0c;一切正常&#xf…...

C\C++ 获取最值

C C 语言的不同类型的最值可以在 limits.h 头文件里找到定义 #include <limits.h>int main() {printf("%d", INT_MAX); // 整数最大值printf("%d", INT_MIN); // 整数最小值 } C C 有模板&#xff0c;可以通过替换下面的 int 和 double&#xff…...

机器学习之无监督学习:九大聚类算法

今天&#xff0c;和大家分享一下机器学习之无监督学习中的常见的聚类方法。 今天&#xff0c;和大家分享一下机器学习之无监督学习中的常见的聚类方法。 在无监督学习中&#xff0c;我们的数据并不带有任何标签&#xff0c;因此在无监督学习中要做的就是将这一系列无标签的数…...

Linux高级管理-搭建网站服务

在Ihternet 网络环境中&#xff0c;Web 服务无疑是最为流行的应用系统。有了Web站点&#xff0c;企业可以充分 展示自己的产品&#xff0c;宣传企业形象。Web站点还为企业提供了与客户交流、电子商务交易平台等丰富 的网络应用。部署与维护Web 服务是运维工程师必须掌握的一个技…...

Windows 系统,TortoiseSVN 无法修改 Log 信息解决方法

使用SVN提交版本信息时&#xff0c;注释内容写的不全。通过右键TortoiseSVN的Show log看到提交的的注释&#xff0c;右键看到Edit log message的选项&#xff0c;然而提交后却给出错误提示&#xff1a; Repository has not been enabled to accept revision propchanges; ask …...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...