[动态规划] (十一) 简单多状态 LeetCode 面试题17.16.按摩师 和 198.打家劫舍
[动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍
文章目录
- [动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍
- 题目分析
- 题目解析
- 状态表示
- 状态转移方程
- 初始化和填表顺序
- 代码实现
- 按摩师
- 打家劫舍
- 总结
注:本题与打家劫舍基本一样,所以只写一道按摩师,末尾只会加上打家劫舍1的代码。
面试题 17.16. 按摩师
198. 打家劫舍
题目分析
(1) 按摩师不能连续接预约
(2) 按摩师可以选择接或者不接预约
(3) 返回预约时间最长的分钟数
题目解析
状态表示
dp[i]:按往常的经验,以i为结尾的最大的服务的分钟数
dp[i]又可以分为:
- f[i]:到
i
位置,接第i
次预约的服务的最大分钟数 - g[i]:到
i
位置,不接第i
次预约的服务的最大分钟数
状态转移方程
- f[i]:
f[i]是到i位置,必须接i
位置的服务的最大分钟数。
由于不能连续接受服务,所以接了i
位置,i-1
位置就不能接受预约了。
g[i-1]正好是到i-1
位置且不接受i-1
预约的最大分钟数,再加上对应的i位置的分钟数就是f[i]。(可以参考后面的图)
f[i] = g[i-1] + nums[i]
- g[i]:
g[i]是到i位置,不接i
位置的服务的最大分钟数。
由于不接i
位置,所以只能看i-1
位置。而i-1
位置也分为接或者不接。
接i-1
位置为f[i-1] (参考状态表示),不接i-1
为g[i-1] (参考状态表示)。
由于求最大值,取它们两个较大的值即可。(可以参考后面的图)
g[i] = max(f[i-1], g[i-1])
初始化和填表顺序
- 初始化
- 访问
i-1
,所以一般初始化前面的位置。
i == 0时,参考状态表示
f[0] = nums[0], g[0] = 0
- 填表顺序
从左向右填表。
看到这里,大家可以尝试实现代码,再来看接下来的内容。
代码实现
按摩师
class Solution {
public:int massage(vector<int>& nums) {//创建dp数组int n = nums.size();if(n == 0) return 0;vector<int> f(n);//选到i位置,必选ivector<int> g(n);//选到i位置,不选i//初始化f[0] = nums[0], g[0] = 0;//填表for(int i = 1; i < n; i++){g[i] = max(f[i-1], g[i-1]);f[i] = g[i-1] + nums[i];}//返回值return max(g[n-1], f[n-1]);}
};
打家劫舍
class Solution {
public:int rob(vector<int>& nums) {//创建dp数组int n = nums.size();vector<int> f(n);vector<int> g(n);//初始化f[0] = nums[0], g[0] = 0;//填表for(int i = 1; i < n; i++){f[i] = g[i-1] + nums[i];g[i] = max(g[i-1], f[i-1]);}//返回值return max(f[n-1], g[n-1]);}
};
总结
细节:注重将问题细分,加上画图理解即可。
相关文章:

[动态规划] (十一) 简单多状态 LeetCode 面试题17.16.按摩师 和 198.打家劫舍
[动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍 文章目录 [动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍题目分析题目解析状态表示状态转移方程初始化和填表顺序 代码实现按摩师打家劫舍 总结 注:本题与…...

【EI会议投稿】第三届计算机、人工智能与控制工程国际学术会议 (CAICE 2024)
The 3rd International Conference on Computer, Artificial Intelligence and Control Engineering (CAICE 2024) 第三届计算机、人工智能与控制工程国际学术会议 第三届计算机、人工智能与控制工程国际学术会议(CAICE 2024)将于2024年1月26-28日在西…...

python 之 列表推导式
文章目录 基本结构示例 1:将列表中的元素乘以 2 添加条件判断示例 2:筛选出偶数并加倍 嵌套列表推导式示例 3:生成九九乘法表 使用条件表达式示例 4:根据条件返回不同的值 镶嵌使用详细介绍基本结构示例生成二维数组多重筛选和操作…...
【左程云算法全讲2】链表、栈、队列、递归、哈希表和有序表
系列综述: 💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。 🥰来源:材料主要源于左程云算法课程进行的,每个知识点的修正和深入主要参考…...

SQL第三次上机作业
1.查询与王利就读同一专业学生的借书证号和姓名 SELECT Lno,Rname FROM Reader WHERE Dept(SELECT DeptFROM ReaderWHERE Rname王利)2.查询比希望出版社出版的所有图书价格都高的图书信息 SELECT * FROM Book WHERE Price>(SELECT MAX(Price)FROM BookWHERE Press希望出版…...
前端事件案例补充
目录 定时器示例 搜索框示例 省市联动 定时器示例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><meta name"viewport" content"widthdevice-width, init…...
3.8 Android eBPF HelloWorld调试(二)
写在前面 我们开发eBPF程序的初衷就是再不改动内核的情况下,将内核监控数据传递给到用户态;像应用进程开发一样开发内核监控程序。 Android开机的时候eBPF程序被加载器加载到内核中,但此时它并没有被附加到内核函数上去,也就是ebpf程序并不会执行,我们可以理解为,它仅仅被…...
xss如何快速提取cookies
<script>alert(111)</script> <img srcx onerroralert(document.cookie)>测试一下baidu的xss <script>alert(111)</script><img srcx οnerrοralert(document.cookie)>...
在 ASP.NET C# 中用Aspose.PDF将 PDF 页面转换为 JPG 图像
PDF 是一种通用格式,通常用于打印和共享文档。 (一)C# PDF to JPG Converter API - 免费下载 Aspose.PDF for .NET是一个强大的 PDF 操作 API,可让您在 .NET 应用程序中创建和处理 PDF 文件。此外,它还允许您将 PDF 文…...

Docker Compose安装milvus向量数据库单机版-milvus基本操作
目录 安装Ubuntu 22.04 LTS在power shell启动milvus容器安装docker desktop下载yaml文件启动milvus容器Milvus管理软件Attu python连接milvus配置下载wget示例导入必要的模块和类与Milvus数据库建立连接创建名为"hello_milvus"的Milvus数据表插入数据创建索引基于向量…...

极致性能优化:前端SSR渲染利器Qwik.js | 京东云技术团队
引言 前端性能已成为网站和应用成功的关键要素之一。用户期望快速加载的页面和流畅的交互,而前端框架的选择对于实现这些目标至关重要。然而,传统的前端框架在某些情况下可能面临性能挑战且存在技术壁垒。 在这个充满挑战的背景下,我们引入…...
ES6~ES13新特性(二)
文章目录 一、ES71.Array Includes2.指数exponentiation运算符 二、ES81.Object values2.Object entries3.String Padding4.Trailing Commas5.Object Descriptors 三、ES9四、ES101.flat flatMap2.Object fromEntries3.trimStart、trimEnd4.其他知识点 五、ES111.BigInt2.Nulli…...

soildwork2022怎么样添加螺纹孔?
1.退出草图模式,点击需要添加螺纹孔的物体面,选中“特征”中的“异形孔向导” 2.选中“孔类型”为“直螺纹孔”,“标准”,“类型”,“孔规格”终止条件等。 3.设置完之后选择“位置” 4.鼠标左键在物体面上点一下&…...

【t5 pytorch版源码学习】t5-pegasus-pytorch源码学习
0. 项目来源 中文生成式预训练模型,以mT5为基础架构和初始权重,通过类似PEGASUS的方式进行预训练。 bert4keras版:t5-pegasus pytorch版:t5-pegasus-pytorch 本次主要学习pytorch版的代码解读。 项目结构: train…...
【springboot】spring的Aop结合Redis实现对短信接口的限流
前言 场景: 为了限制短信验证码接口的访问次数,防止被刷,结合Aop和redis根据用户ip对用户限流 1.准备工作 首先我们创建一个 Spring Boot 工程,引入 Web 和 Redis 依赖,同时考虑到接口限流一般是通过注解来标记,而注解…...
【MedusaSTears】怎么禁用edge浏览器截图功能?
版本 Microsoft Edge 版本 119.0.2151.44 (正式版本) (64 位) Ctrl Shift S 竟然是浏览器的截屏? 特么的啥时候多了这么个快捷键? 然后还没办法禁用,真TMD傻哔 edge://settings/accessibility解决方式: 参考资料: 怎么禁用edge浏览器截图功能? 您好&#x…...

【计算机网络】(谢希仁第八版)第三章课后习题答案
第三章 1.数据链路(即逻辑链路)与链路(即物理链路)有何区别? “电路接通了”与”数据链路接通了”的区别何在? 答:数据链路与链路的区别在于数据链路出链路外,还必须有一些必要的规程来控制数据的传输,因此,数据链路比链路多了…...
批量异步任务处理
当我们在项目中遇到很多业务同时处理,如果是串行肯定是影响性能的,这时候就需要异步执行了,说道异步肯定就有很多方案了 方案一: 比如使用spring的异步注解,比如下面的代码,每个方法上面都是异步注解,当时…...

宜昌市公安局、点军区政府与中科升哲达成战略合作,共建视频图像联合创新实验室
11月3日,宜昌视频图像联合创新战略合作签约仪式在宜昌市公安局举行。 宜昌市副市长、市公安局党委书记、局长上官福令,市公安局党委副书记、副局长龚海波,宜昌市点军区委书记万红,点军区委副书记、区长黄文云,升哲科技…...

java版小程序商城免费搭建-直播商城平台规划及常见的营销模式有哪些?电商源码/小程序/三级分销
1. 涉及平台 平台管理、商家端(PC端、手机端)、买家平台(H5/公众号、小程序、APP端(IOS/Android)、微服务平台(业务服务) 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前端框架…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...

基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...