动态规划 —— dp问题-按摩师
1. 按摩师
题目链接:
面试题 17.16. 按摩师 - 力扣(LeetCode)
https://leetcode.cn/problems/the-masseuse-lcci/description/
2. 算法原理
状态表示:以某一个位置为结尾或者以某一个位置为起点
dp[i]表示:选择到i位置的时候,此时的最长预约时长分两种情况:
1.f[i]表示:选择到i位置的时候,当前位置nums[i]必选,此时的最长预约时长
2.g[i]表示:选择到i位置的时候,当前位置nums[i]不选,此时的最长预约时长
2. 状态转移方程
根据最近的一步来划分问题:
到达dp[i][j]有两种情况:
1. f[i]=g[i-1] + nums[i]
2. g[i]:a. 当选择i-1的位置时:f[i-1]
b.当不选择i-1的位置时:g[i-1]
g[i]=max(f[i-1],g[i-1])
3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行
本题初始化为:f[0]=nums[0] g[0]在vector填表的时候默认为0
4. 填表顺序
本题的填表顺序是:从左往右,两个表一起填
5. 返回值 :题目要求 + 状态表示
本题的返回值是:max(f[n-1],g[n-1])
3.代码
动态规划的固定四步骤:1. 创建一个dp表
2. 在填表之前初始化
3. 填表(填表方法:状态转移方程)
4. 确定返回值
class Solution {
public:int massage(vector<int>& nums) {int n=nums.size();//处理一下边界情况if(n==0) return 0;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]);}
};
完结撒花~
相关文章:

动态规划 —— dp问题-按摩师
1. 按摩师 题目链接: 面试题 17.16. 按摩师 - 力扣(LeetCode)https://leetcode.cn/problems/the-masseuse-lcci/description/ 2. 算法原理 状态表示:以某一个位置为结尾或者以某一个位置为起点 dp[i]表示:选择到i位置…...
SQL 语法学习
在当今数字化的时代,数据的管理和分析变得至关重要。而 SQL(Structured Query Language),即结构化查询语言,作为一种用于管理关系型数据库的强大工具,掌握它对于从事数据相关工作的人来说是一项必备技能。在…...

MYSQL---TEST5(Trigger触发器Procedure存储过程综合练习)
触发器Trigger 数据库mydb16_trigger创建 表的创建 goods create table goods( gid char(8) primary key, #商品号 name varchar(10), #商品名 price decimal(8,2), #价格 num int;) #数量orders create tabl…...

蓝桥杯 区间移位--二分、枚举
题目 代码 #include <stdio.h> #include <string.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; struct node{ int a,b; }; vector<node> q; bool cmp(node x,node y){ return x.b <…...
Nginx 报错400 Request Header Or Cookie Too Large
错误的原因: 1、可能是你的网络DNS配置错误。 2、由request header过大所引起,request过大,通常是由于cookie中写入了较大的值所引起的。 3、访问太频繁,浏览器的缓存量太大,产生错误。 解决办法: 1、清…...
【Redis】一种常见的Redis分布式锁原理简述
本文主要简述一下基于set命令的Redis分布式锁的原理。 一,a线程持有的锁不要被b线程同时持有→setnx 抢锁的时候,最核心的就是,a线程持有的锁不要被b线程同时持有,放在基于set命令的redis分布式锁中来看,就是“如果锁…...

HOT100_最大子数组和
class Solution {public int maxSubArray(int[] nums) {int[] dp new int[nums.length];int res nums[0];dp[0] nums[0];for(int i 1; i< nums.length; i){dp[i] Math.max(nums[i] ,dp[i-1] nums[i]);res Math.max(res, dp[i]);}return res;} }...
DiskGenius工具扩容Mac OS X Apple APFS分区
DiskGenius是一款功能强大的磁盘分区工具,它支持Windows和Mac OS X系统,可以用于管理硬盘分区,包括扩容Mac OS X的Apple APFS分区。然而,直接使用DiskGenius来扩容Mac OS X的APFS分区可能存在一定的风险,因为不是专门为…...
从零开始的LeetCode刷题日记:70. 爬楼梯
一.相关链接 题目链接:70. 爬楼梯 二.心得体会 这道题还是动规五部曲。 1.首先是dp数组及其下标的含义,dp记录了每层楼梯对应的爬的方法,每个下标存储每个对应楼层。 2.然后是递归公式,其实每一层楼都是可以从下面一层和下面…...

Unity照片墙效果
Unity照片墙效果,如下效果展示 。 工程源码...

【自动化利器】12个评估大语言模型(LLM)质量的自动化框架
LLM评估是指在人工智能系统中评估和改进语言和语言模型的过程。在人工智能领域,特别是在自然语言处理(NLP)及相关领域,LLM评估具有至高无上的地位。通过评估语言生成和理解模型,LLM评估有助于细化人工智能驱动的语言相…...
【1】基础概念
文章目录 一、特点二、基础语法注意三、官方编程指南四、go 语言标准库 API 一、特点 golang 一个 go 文件都要归属到一个包,需要进行申明。天然的并发:golang 从语言层面支持大并发。每个 go 文件都必须要归属到一个包中。执行 go 文件:go …...

HTML 文档规范与解析模式:DOCTYPE、<html> 标签以及结构化页面
文章目录 `<!DOCTYPE html>` 文档类型声明标准模式与怪异模式HTML5 的简化声明`<html>` 标签`<head>` 标签`<body>` 标签小结<!DOCTYPE html> 文档类型声明 在 HTML 文档中,<!DOCTYPE html> 是一个重要的文档类型声明,主要用于告知浏览…...
大模型微调技术 --> 脉络
Step1:脉络 微调技术从最早期的全模型微调演变成如今的各种参数高效微调(PEFT)方法,背后是为了应对大模型中的计算、存储和数据适应性的挑战 1.为什么有微调? 深度学习模型越来越大,尤其是 NLP 中的预训练语言模型(BERT, GPT)系列。如果从…...

不要只知道deepl翻译,这里有10个专业好用的翻译工具等着你。
deepl翻译的优点还是有很多的,比如翻译的准确性很高,支持翻译的语言有很多,并且支持翻译文件和文本。但是现在翻译工具那么多,大家需要翻译的场景也有很多,怎么能只拥有一个翻译工具呢。所以在这里我帮助大家寻找了一波…...

第二节 管道符、重定向与环境变量
1.重定向技术的 5 种模式 (1)标准覆盖输出重定向 (2)标准追加输出重定向 (3)错误覆盖输出重定向 (4)错误追加输出重定向 (5)输入重定向2.输入输出重定向 输入…...

Linux 服务器使用指南:从入门到登录
🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟 🚩博主致力于用通俗易懂且不失专业性的文字,讲解计算机领域那些看似枯燥的知识点🚩 目录 一…...

QT 如何使QLabel的文字垂直显示
想要实现QLabel文字的垂直显示,可以通过使用“文字分割填充换行符”的方式来实现QLabel文字垂直显示的效果,下面是效果图: 具体实现代码: #include "mainwindow.h" #include "ui_mainwindow.h"MainWindow:…...

蓬勃发展:移动开发——关于软件开发你需要知道些什么
一、前言 移动开发一直都是软件开发领域中最有趣的领域之一,这是因为: 1、移动开发为“只有一个人”的开发团队提供了一个非常独特的机会,让他可以在相对较短的时间内建立一个实际的、可用的、有意义的应用程序; 2、移动开发也代…...
1095. 山脉数组中查找目标值
目录 题目解法lambda在这是怎么用的? 题目 (这是一个 交互式问题 ) 你可以将一个数组 arr 称为 山脉数组 当且仅当: arr.length > 3 存在一些 0 < i < arr.length - 1 的 i 使得: arr[0] < arr[1] <…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...

android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...