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

「动态规划」按摩师

力扣原题链接,点击跳转。

一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列nums,总共有n个预约,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。

我们用动态规划的思想解决这个问题。首先创建dp表,确定状态表示,很自然地想到,可以用dp[i]表示一直收到下标为i的请求后,接受的预约的最长总时长。然而,这么想是不够的,因为对于每个预约,都有可能接受或者不接受。所以要分类讨论:用f[i]表示接受下标为i的请求后,接受的预约的最长总时长;用g[i]表示不接受下标为i的请求后,接受的预约的最长总时长。

接着推导状态转移方程。对于f[i],接受了下标为i的预约,说明没有接受下标为i-1的预约,此时接受的预约的最长总时长应为g[i-1]+nums[i]。对于g[i],不接受下标为i的预约,有可能接受了下标为i-1的预约,也有可能不接受下标为i-1的预约,由于要求最长总时长,所以g[i]=max(f[i-1],g[i-1])。

初始化时,只需把f[0]初始化成nums[0],g[0]初始化成0,再从左往右同时填f表和g表。最后,返回max(f[n-1],g[n-1])。

class Solution
{
public:int massage(vector<int>& nums){int n = nums.size();// 处理边界情况if (n == 0)return 0;// 创建dp表vector<int> f(n);auto g = f;// 初始化f[0] = nums[0];// 填表for (int i = 1; i < n; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};

相关文章:

「动态规划」按摩师

力扣原题链接&#xff0c;点击跳转。 一个有名的按摩师会收到源源不断的预约请求&#xff0c;每个预约都可以选择接或不接。在每次预约服务之间要有休息时间&#xff0c;因此她不能接受相邻的预约。给定一个预约请求序列nums&#xff0c;总共有n个预约&#xff0c;替按摩师找到…...

小程序-滚动触底-页面列表数据无限加载

// index/index.vue <template> <!-- 自定义导航栏 --> <CustomNavbar /> <scroll-view scrolltolower"onScrolltolower" scroll-y class"scroll-view"> <!-- 猜你喜欢 --> <Guess ref"guessRef" /> </s…...

监控上网的软件有哪些?含泪推荐的电脑监控软件

监控上网的软件有很多&#xff0c;企业选择的时候应该遵循什么样的原则呢&#xff1f;鄙人愚见&#xff0c;认为以下四项原则是选择监控软件时首要考虑的。 1、功能需求&#xff1a; 监控软件不应该只是起到控制上网的作用&#xff0c;因为一些泄密行为可能是通过USB接口、打印…...

linux系统防火墙开放端口命令

目录 linux相关命令参考文章1.开放端口1.1 开发单个端口1.2 一次性开放多个端口 2.保存设置3.查看所有开放的端口4.查看防火墙状态 linux相关命令参考文章 管理、设置防火墙规则&#xff08;firewalld&#xff09;: https://download.csdn.net/blog/column/8489557/137911049 i…...

WebGL渲染引擎优化方向——渲染帧率的优化

作者&#xff1a;caven chen 对此内容感兴趣还可以看前文&#xff1a; WebGL渲染引擎优化方向——加载性能优化 前言 WebGL 是一种强大的图形渲染技术&#xff0c;可以在浏览器中快速渲染复杂的 3D 场景。但是&#xff0c;由于 WebGL 的高性能和高质量要求&#xff0c;如果…...

【文献阅读】ESG评级分化和企业绿色创新

ESG评级分化和企业绿色创新 摘要 &#xff08;1&#xff09;本研究通过实证探讨了ESG评级差异是否以及如何影响企业绿色创新。以中国上市公司为样本&#xff0c;我们发现ESG评级差异对企业绿色创新有积极的影响 。经过几次稳健性检查后&#xff0c;该结果仍然成立。 &#xff…...

2024-5-6-从0到1手写配置中心Config之实现配置中心客户端

配置加载原理 在Spring中PropertySource类实现了所有属性的实例化。 启动赋值&#xff1a; 定义自定义属性配置源&#xff0c;从config-server获取全局属性&#xff1b;Spring启动时&#xff0c;插入自定义属性配置源&#xff1b;绑定属性会优先使用&#xff0c;给自定义属性…...

【HarmonyOS4学习笔记】《HarmonyOS4+NEXT星河版入门到企业级实战教程》课程学习笔记(十一)

课程地址&#xff1a; 黑马程序员HarmonyOS4NEXT星河版入门到企业级实战教程&#xff0c;一套精通鸿蒙应用开发 &#xff08;本篇笔记对应课程第 18 节&#xff09; P18《17.ArkUI-状态管理Observed 和 ObjectLink》 第一件事&#xff1a;嵌套对象的类型上加上 Observed 装饰器…...

Amesim示例篇-案例1:空间中的铝块散热

前言 本文将通过一个案例继续对Thermal库的元件进一步讲解。 案例1&#xff1a;一个300mm*300mm*1000mm&#xff08;长*宽*高&#xff09;的铝板初始温度为45℃&#xff0c;竖直在环境为25℃的空间内静置60min。对流换热系数设置为5W/m2K。本文将通过两种建模方法对铝块的温度…...

深度神经网络——什么是自动编码器?

自动编码器 自动编码器&#xff08;Autoencoders&#xff09;是无监督学习领域中一种重要的神经网络架构&#xff0c;它们主要用于数据压缩和特征学习。 自动编码器的定义&#xff1a; 自动编码器是一种无监督机器学习算法&#xff0c;它通过反向传播进行训练&#xff0c;目标…...

初见flyway

flyway (一种数据库版本控制工具 document) 两种文件 V 和 R V: V 开头是不可重复执行的文件&#xff0c;每次修改完都该更改名称 R: R 开头是可重复执行的文件&#xff0c;需要保证内部sql都是可以重复执行的 名称格式&#xff1a; V__table_name.sql, R__table_name.sql …...

9.6 Go语言入门(数组、切片和指针)

Go语言入门&#xff08;数组、切片和指针&#xff09; 目录五、数组、切片和指针1. 数组1.1 声明和初始化数组1.2 访问和修改数组元素1.3 多维数组 2. 切片2.1 声明和初始化切片2.2 访问和修改切片元素2.3 切片操作2.4 切片的追加和拷贝 3. 指针3.1 声明和初始化指针3.2 指针与…...

Web面试题(一)

一&#xff1a;以前公司的测试流程&#xff1f; &#xff08;&#xff11;&#xff09;问题分析 面试官主要为了考察候选者对软件测试流程的理解和掌握程度。 &#xff08;&#xff12;&#xff09;核心答案讲解 &#xff11;&#xff09;需求分析与评审 &#xff12;&#xff…...

【Crypto】一眼就解密

文章目录 前言一眼就解密解题感悟 前言 Basic写累了&#xff0c;写写别的 一眼就解密 一眼md5试一试 小小flag 拿下&#xff01; 解题感悟 30秒搞定...

虚拟ECU:彻底改变汽车软件开发与测试

汽车开发领域有着垂直性较强的一系列需求&#xff0c;其中最为瞩目的需求之一就是对安全高效的软件测试方法的需求。传统的汽车开发偏向使用硬件原型与真实ECU进行软件测试&#xff0c;但由于硬件设备往往在开发周期的中后阶段才生产完成&#xff0c;给汽车开发带来了成本与时间…...

【SQL Server001】SQLServer2016常用函数实战总结(已更新)

1.熟悉、梳理、总结下SQL Server相关知识体系。 2.日常研发过程中使用较少&#xff0c;随着时间的推移&#xff0c;很快就忘得一干二净&#xff0c;所以梳理总结下&#xff0c;以备日常使用参考 3.欢迎批评指正&#xff0c;跪谢一键三连&#xff01; 总结源文件资源下载地址&am…...

51单片机简单控制180度舵机

代码&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1K9dg2NwRhy49db_O_hqv-g?pwd1234 提取码&#xff1a;1234 一、路线 我在了解这个舵机之前最像想看到的是一个完全的路径。 比如我想学习b站上那个智能门锁&#xff0c;那就得每个模块的基本代码都会才能结合各…...

PCL 常用小知识

文章目录 一、时间计算二、实现类似`pcl::PointCloud::Ptr`和`pcl::PointCloud`的两个类相互转换三、查找点云的x,y,z的极值四、知道需要保存点的索引,从原点云中拷贝点到新点云五、从点云里删除和添加点六、对点云进行全局或局部变换七、链接两个点云字段(两点云大小必须相…...

rbd块设备数据IO流程(client端)

一、rbd内核驱动写入流程 1&#xff09;初始化 首先是rbd驱动的初始化工作&#xff1a;包括验证libceph的兼容性&#xff0c;分配内存&#xff0c;在sysfs中创建块设备控制文件、创建工作队列rbd_wq并调用INIT_WORK初始化它 module_init(rbd_init); static int __init rbd_i…...

数据仓库、数据中台、大数据平台之间的关系

数据行业经常会出现数据仓库、数据中台、大数据平台等概念&#xff0c;容易产生疑问&#xff0c;它们中间是相等&#xff0c;还是包含的关系&#xff1f; 数据中台和数据仓库概念的关系 数据中台概念是包含数据仓库的&#xff0c;数据仓库是数据中台中的一部分&#xff0c;包含…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...