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

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

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

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