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

[动态规划] (十一) 简单多状态 LeetCode 面试题17.16.按摩师 和 198.打家劫舍

[动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍

文章目录

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

注:本题与打家劫舍基本一样,所以只写一道按摩师,末尾只会加上打家劫舍1的代码。

面试题 17.16. 按摩师
198. 打家劫舍
image-20231107161334755

题目分析

(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])

image-20231107164235791

初始化和填表顺序
  • 初始化
  • 访问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]);}
};

image-20231107163822064

打家劫舍
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]);}
};

image-20231107163851645

总结

细节:注重将问题细分,加上画图理解即可。

相关文章:

[动态规划] (十一) 简单多状态 LeetCode 面试题17.16.按摩师 和 198.打家劫舍

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

【EI会议投稿】第三届计算机、人工智能与控制工程国际学术会议 (CAICE 2024)

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

python 之 列表推导式

文章目录 基本结构示例 1&#xff1a;将列表中的元素乘以 2 添加条件判断示例 2&#xff1a;筛选出偶数并加倍 嵌套列表推导式示例 3&#xff1a;生成九九乘法表 使用条件表达式示例 4&#xff1a;根据条件返回不同的值 镶嵌使用详细介绍基本结构示例生成二维数组多重筛选和操作…...

【左程云算法全讲2】链表、栈、队列、递归、哈希表和有序表

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于左程云算法课程进行的&#xff0c;每个知识点的修正和深入主要参考…...

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 是一种通用格式&#xff0c;通常用于打印和共享文档。 &#xff08;一&#xff09;C# PDF to JPG Converter API - 免费下载 Aspose.PDF for .NET是一个强大的 PDF 操作 API&#xff0c;可让您在 .NET 应用程序中创建和处理 PDF 文件。此外&#xff0c;它还允许您将 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 | 京东云技术团队

引言 前端性能已成为网站和应用成功的关键要素之一。用户期望快速加载的页面和流畅的交互&#xff0c;而前端框架的选择对于实现这些目标至关重要。然而&#xff0c;传统的前端框架在某些情况下可能面临性能挑战且存在技术壁垒。 在这个充满挑战的背景下&#xff0c;我们引入…...

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.退出草图模式&#xff0c;点击需要添加螺纹孔的物体面&#xff0c;选中“特征”中的“异形孔向导” 2.选中“孔类型”为“直螺纹孔”&#xff0c;“标准”&#xff0c;“类型”&#xff0c;“孔规格”终止条件等。 3.设置完之后选择“位置” 4.鼠标左键在物体面上点一下&…...

【t5 pytorch版源码学习】t5-pegasus-pytorch源码学习

0. 项目来源 中文生成式预训练模型&#xff0c;以mT5为基础架构和初始权重&#xff0c;通过类似PEGASUS的方式进行预训练。 bert4keras版&#xff1a;t5-pegasus pytorch版&#xff1a;t5-pegasus-pytorch 本次主要学习pytorch版的代码解读。 项目结构&#xff1a; train…...

【springboot】spring的Aop结合Redis实现对短信接口的限流

前言 场景: 为了限制短信验证码接口的访问次数&#xff0c;防止被刷&#xff0c;结合Aop和redis根据用户ip对用户限流 1.准备工作 首先我们创建一个 Spring Boot 工程&#xff0c;引入 Web 和 Redis 依赖&#xff0c;同时考虑到接口限流一般是通过注解来标记&#xff0c;而注解…...

【MedusaSTears】怎么禁用edge浏览器截图功能?

版本 Microsoft Edge 版本 119.0.2151.44 (正式版本) (64 位) Ctrl Shift S 竟然是浏览器的截屏? 特么的啥时候多了这么个快捷键? 然后还没办法禁用,真TMD傻哔 edge://settings/accessibility解决方式: 参考资料: 怎么禁用edge浏览器截图功能&#xff1f; 您好&#x…...

【计算机网络】(谢希仁第八版)第三章课后习题答案

第三章 1.数据链路(即逻辑链路)与链路(即物理链路)有何区别? “电路接通了”与”数据链路接通了”的区别何在? 答&#xff1a;数据链路与链路的区别在于数据链路出链路外&#xff0c;还必须有一些必要的规程来控制数据的传输&#xff0c;因此&#xff0c;数据链路比链路多了…...

批量异步任务处理

当我们在项目中遇到很多业务同时处理&#xff0c;如果是串行肯定是影响性能的&#xff0c;这时候就需要异步执行了&#xff0c;说道异步肯定就有很多方案了 方案一&#xff1a; 比如使用spring的异步注解&#xff0c;比如下面的代码,每个方法上面都是异步注解&#xff0c;当时…...

宜昌市公安局、点军区政府与中科升哲达成战略合作,共建视频图像联合创新实验室

11月3日&#xff0c;宜昌视频图像联合创新战略合作签约仪式在宜昌市公安局举行。 宜昌市副市长、市公安局党委书记、局长上官福令&#xff0c;市公安局党委副书记、副局长龚海波&#xff0c;宜昌市点军区委书记万红&#xff0c;点军区委副书记、区长黄文云&#xff0c;升哲科技…...

java版小程序商城免费搭建-直播商城平台规划及常见的营销模式有哪些?电商源码/小程序/三级分销

1. 涉及平台 平台管理、商家端&#xff08;PC端、手机端&#xff09;、买家平台&#xff08;H5/公众号、小程序、APP端&#xff08;IOS/Android&#xff09;、微服务平台&#xff08;业务服务&#xff09; 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前端框架…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...