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

动态规划 —— dp问题-按摩师

1. 按摩师

题目链接:

面试题 17.16. 按摩师 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://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. 按摩师 题目链接&#xff1a; 面试题 17.16. 按摩师 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/the-masseuse-lcci/description/ 2. 算法原理 状态表示&#xff1a;以某一个位置为结尾或者以某一个位置为起点 dp[i]表示&#xff1a;选择到i位置…...

SQL 语法学习

在当今数字化的时代&#xff0c;数据的管理和分析变得至关重要。而 SQL&#xff08;Structured Query Language&#xff09;&#xff0c;即结构化查询语言&#xff0c;作为一种用于管理关系型数据库的强大工具&#xff0c;掌握它对于从事数据相关工作的人来说是一项必备技能。在…...

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&#xff1b;&#xff09; #数量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

错误的原因&#xff1a; 1、可能是你的网络DNS配置错误。 2、由request header过大所引起&#xff0c;request过大&#xff0c;通常是由于cookie中写入了较大的值所引起的。 3、访问太频繁&#xff0c;浏览器的缓存量太大&#xff0c;产生错误。 解决办法&#xff1a; 1、清…...

【Redis】一种常见的Redis分布式锁原理简述

本文主要简述一下基于set命令的Redis分布式锁的原理。 一&#xff0c;a线程持有的锁不要被b线程同时持有→setnx 抢锁的时候&#xff0c;最核心的就是&#xff0c;a线程持有的锁不要被b线程同时持有&#xff0c;放在基于set命令的redis分布式锁中来看&#xff0c;就是“如果锁…...

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是一款功能强大的磁盘分区工具&#xff0c;它支持Windows和Mac OS X系统&#xff0c;可以用于管理硬盘分区&#xff0c;包括扩容Mac OS X的Apple APFS分区。然而&#xff0c;直接使用DiskGenius来扩容Mac OS X的APFS分区可能存在一定的风险&#xff0c;因为不是专门为…...

从零开始的LeetCode刷题日记:70. 爬楼梯

一.相关链接 题目链接&#xff1a;70. 爬楼梯 二.心得体会 这道题还是动规五部曲。 1.首先是dp数组及其下标的含义&#xff0c;dp记录了每层楼梯对应的爬的方法&#xff0c;每个下标存储每个对应楼层。 2.然后是递归公式&#xff0c;其实每一层楼都是可以从下面一层和下面…...

Unity照片墙效果

Unity照片墙效果&#xff0c;如下效果展示 。 工程源码...

【自动化利器】12个评估大语言模型(LLM)质量的自动化框架

LLM评估是指在人工智能系统中评估和改进语言和语言模型的过程。在人工智能领域&#xff0c;特别是在自然语言处理&#xff08;NLP&#xff09;及相关领域&#xff0c;LLM评估具有至高无上的地位。通过评估语言生成和理解模型&#xff0c;LLM评估有助于细化人工智能驱动的语言相…...

【1】基础概念

文章目录 一、特点二、基础语法注意三、官方编程指南四、go 语言标准库 API 一、特点 golang 一个 go 文件都要归属到一个包&#xff0c;需要进行申明。天然的并发&#xff1a;golang 从语言层面支持大并发。每个 go 文件都必须要归属到一个包中。执行 go 文件&#xff1a;go …...

HTML 文档规范与解析模式:DOCTYPE、<html> 标签以及结构化页面

文章目录 `<!DOCTYPE html>` 文档类型声明标准模式与怪异模式HTML5 的简化声明`<html>` 标签`<head>` 标签`<body>` 标签小结<!DOCTYPE html> 文档类型声明 在 HTML 文档中,<!DOCTYPE html> 是一个重要的文档类型声明,主要用于告知浏览…...

大模型微调技术 --> 脉络

Step1:脉络 微调技术从最早期的全模型微调演变成如今的各种参数高效微调(PEFT)方法&#xff0c;背后是为了应对大模型中的计算、存储和数据适应性的挑战 1.为什么有微调&#xff1f; 深度学习模型越来越大&#xff0c;尤其是 NLP 中的预训练语言模型(BERT, GPT)系列。如果从…...

不要只知道deepl翻译,这里有10个专业好用的翻译工具等着你。

deepl翻译的优点还是有很多的&#xff0c;比如翻译的准确性很高&#xff0c;支持翻译的语言有很多&#xff0c;并且支持翻译文件和文本。但是现在翻译工具那么多&#xff0c;大家需要翻译的场景也有很多&#xff0c;怎么能只拥有一个翻译工具呢。所以在这里我帮助大家寻找了一波…...

第二节 管道符、重定向与环境变量

1.重定向技术的 5 种模式 &#xff08;1&#xff09;标准覆盖输出重定向 &#xff08;2&#xff09;标准追加输出重定向 &#xff08;3&#xff09;错误覆盖输出重定向 &#xff08;4&#xff09;错误追加输出重定向 &#xff08;5&#xff09;输入重定向2.输入输出重定向 输入…...

Linux 服务器使用指南:从入门到登录

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; &#x1f6a9;博主致力于用通俗易懂且不失专业性的文字&#xff0c;讲解计算机领域那些看似枯燥的知识点&#x1f6a9; 目录 一…...

QT 如何使QLabel的文字垂直显示

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

蓬勃发展:移动开发——关于软件开发你需要知道些什么

一、前言 移动开发一直都是软件开发领域中最有趣的领域之一&#xff0c;这是因为&#xff1a; 1、移动开发为“只有一个人”的开发团队提供了一个非常独特的机会&#xff0c;让他可以在相对较短的时间内建立一个实际的、可用的、有意义的应用程序&#xff1b; 2、移动开发也代…...

1095. 山脉数组中查找目标值

目录 题目解法lambda在这是怎么用的&#xff1f; 题目 &#xff08;这是一个 交互式问题 &#xff09; 你可以将一个数组 arr 称为 山脉数组 当且仅当&#xff1a; arr.length > 3 存在一些 0 < i < arr.length - 1 的 i 使得&#xff1a; arr[0] < arr[1] <…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...

ZYNQ学习记录FPGA(二)Verilog语言

一、Verilog简介 1.1 HDL&#xff08;Hardware Description language&#xff09; 在解释HDL之前&#xff0c;先来了解一下数字系统设计的流程&#xff1a;逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端&#xff0c;在这个过程中就需要用到HDL&#xff0c;正文…...