[动态规划] (十一) 简单多状态 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. 前端框架…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
