当前位置: 首页 > 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 …...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

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 …...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...