Leetcode算法题:按摩师(动态规划java)

2024-01-08 07:59

本文主要是介绍Leetcode算法题:按摩师(动态规划java),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

按摩师## 标题
题目描述:一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。在这里插入图片描述
解题方法:动态规划

解题思路:

  • 第一步

:开一个二维数组dp[n][2]
由于当前这一天有按摩师有两种选择:
(1)接预约;
(2)不接预约。但根据题意,今天是否接预约,是受到昨天影响的。为了消除这种影响,我们在状态数组要设置这个维度。

dp[i][0] 表示:区间 [0,i] 里接受预约请求,并且下标为 i 的这一天不接受预约的最大时长;
dp[i][1] 表示:区间 [0,i] 里接受预约请求,并且下标为 i 的这一天接受预约的最大时长。

  • 第二步

:根据具体情况写出状态转移方程
今天不接受预约:或者是昨天不接受预约,或者是昨天接受了预约,取二者最大值,即:

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

今天接受预约:只需要从昨天不接受预约转移而来,加上今天的时常,即:

dp[i][1] = dp[i - 1][0] + nums[i]
  • 第三步:初始条件和边界情况
dp[0][0]=0;
dp[0][1]=nums[0];
  • 第四步:计算顺序

dp[0][1] dp[1][1]…

代码

class Solution {public int massage(int[] nums) {//开一个二维数组,第二维度解决其后效性,通常情况下,容易受到其他因素干扰的可以增加第二个维度int n=nums.length;        int[][]dp=new int[n][2];//开一个二维数组;if(n==0)return 0;if(n==1)return nums[0];dp[0][0]=0;dp[0][1]=nums[0];for(int i=1;i<n;i++){//第i个预约不接受dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);//第i个预约接受dp[i][1]=dp[i-1][0]+nums[i];}return(Math.max(dp[n-1][1],dp[n-1][0]));}
}

下面总结一下动态规划的基本步骤:
在这里插入图片描述
这是一道简单的动态规划问题做出的总结!谢谢大家阅读到这里!

这篇关于Leetcode算法题:按摩师(动态规划java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/582794

相关文章

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

在Spring Boot中浅尝内存泄漏的实战记录

《在SpringBoot中浅尝内存泄漏的实战记录》本文给大家分享在SpringBoot中浅尝内存泄漏的实战记录,结合实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录使用静态集合持有对象引用,阻止GC回收关键点:可执行代码:验证:1,运行程序(启动时添加JVM参数限制堆大小):2,访问 htt

SpringBoot集成Milvus实现数据增删改查功能

《SpringBoot集成Milvus实现数据增删改查功能》milvus支持的语言比较多,支持python,Java,Go,node等开发语言,本文主要介绍如何使用Java语言,采用springboo... 目录1、Milvus基本概念2、添加maven依赖3、配置yml文件4、创建MilvusClient

浅析Java中如何优雅地处理null值

《浅析Java中如何优雅地处理null值》这篇文章主要为大家详细介绍了如何结合Lambda表达式和Optional,让Java更优雅地处理null值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录场景 1:不为 null 则执行场景 2:不为 null 则返回,为 null 则返回特定值或抛出异常场景

SpringMVC获取请求参数的方法

《SpringMVC获取请求参数的方法》:本文主要介绍SpringMVC获取请求参数的方法,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下... 目录1、通过ServletAPI获取2、通过控制器方法的形参获取请求参数3、@RequestParam4、@

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

springboot项目中常用的工具类和api详解

《springboot项目中常用的工具类和api详解》在SpringBoot项目中,开发者通常会依赖一些工具类和API来简化开发、提高效率,以下是一些常用的工具类及其典型应用场景,涵盖Spring原生... 目录1. Spring Framework 自带工具类(1) StringUtils(2) Coll

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

SpringBoot条件注解核心作用与使用场景详解

《SpringBoot条件注解核心作用与使用场景详解》SpringBoot的条件注解为开发者提供了强大的动态配置能力,理解其原理和适用场景是构建灵活、可扩展应用的关键,本文将系统梳理所有常用的条件注... 目录引言一、条件注解的核心机制二、SpringBoot内置条件注解详解1、@ConditionalOn

通过Spring层面进行事务回滚的实现

《通过Spring层面进行事务回滚的实现》本文主要介绍了通过Spring层面进行事务回滚的实现,包括声明式事务和编程式事务,具有一定的参考价值,感兴趣的可以了解一下... 目录声明式事务回滚:1. 基础注解配置2. 指定回滚异常类型3. ​不回滚特殊场景编程式事务回滚:1. ​使用 TransactionT