力扣(leetcode)每日一题 983 最低票价 |动态规划
983. 最低票价
题干
在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days
的数组给出。每一项是一个从 1
到 365
的整数。
火车票有 三种不同的销售方式 :
- 一张 为期一天 的通行证售价为
costs[0]
美元; - 一张 为期七天 的通行证售价为
costs[1]
美元; - 一张 为期三十天 的通行证售价为
costs[2]
美元。
通行证允许数天无限制的旅行。 例如,如果我们在第 2
天获得一张 为期 7 天 的通行证,那么我们可以连着旅行 7 天:第 2
天、第 3
天、第 4
天、第 5
天、第 6
天、第 7
天和第 8
天。
返回 你想要完成在给定的列表 days
中列出的每一天的旅行所需要的最低消费 。
示例 1:
**输入:**days = [1,4,6,7,8,20], costs = [2,7,15]
**输出:**11
解释:
例如,这里有一种购买通行证的方法,可以让你完成你的旅行计划:
在第 1 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 1 天生效。
在第 3 天,你花了 costs[1] = $7 买了一张为期 7 天的通行证,它将在第 3, 4, …, 9 天生效。
在第 20 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 20 天生效。
你总共花了 $11,并完成了你计划的每一天旅行。
题解
暴力递归改动态规划
这里非常不好做的是边界的判断
出现问题后也不好定位
public static int mincostTickets(int[] days, int[] costs) { return f(0, days, costs);
} public static int f(int index, int[] days, int[] costs) { if (index == days.length) { return 0; } // 使用一天的花费 int res = f(index + 1, days, costs) + costs[0]; for (int i = index; i < days.length; i++) { if (days[i] - days[index] < 7) { int f2 = f(i + 1, days, costs) + costs[1]; res = Math.min(res, f2); } else { break; } }for (int i = index; i < days.length; i++) { if (days[i] - days[index] < 15) { int f2 = f(i + 1, days, costs) + costs[2]; res = Math.min(res, f2); } else { break; } }return res;
}
这个暴力递归的写法有个很严重的问题,不应该循环进行递归。
public static int mincostTickets(int[] days, int[] costs) { int length = days.length; int[] dp = new int[length + 1]; dp[length] = 0; for (int index = length - 1; index >= 0; index--) { int res = dp[index + 1] + costs[0]; int index2 = index; while (index2 < length && days[index2] - days[index] < 7) { // 和当前相等肯定可以进来,因此index2已经进行+1操作,可以直接传递下去 index2++; } int f2 = dp[index2] + costs[1]; res = Math.min(res, f2); int index3 = index; while (index3 < length && days[index3] - days[index] < 30) { index3++; } int f3 = dp[index3] + costs[2]; res = Math.min(res, f3); dp[index] = res; } return dp[0];
}
这里换成dp的时候已经纠正过来了
这里的写法还有一个问题,index2和index3 每次都是从index开始遍历的
但是用时更快的写法是index2,index3从0开始不回退。index也是从0开始
比如 index为0时候 index3为9,满足了30天的条件,当index为1的时候,难道index为3以及之前还不能满足吗。显然不会。
总结
这个题目的days[index] < 7
用小于号还是小于等于,递归下去是否还要加1的边界判断比较容易绕晕
另外,7天的签证可以比1天的签证便宜,所有必须3种情况都递归下去
相关文章:

力扣(leetcode)每日一题 983 最低票价 |动态规划
983. 最低票价 题干 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车票有 三种不同的销售方式 : 一张 为期一天 的通…...

【漏洞复现】VEXUS多语言货币交易所存在未授权访问漏洞
漏洞描述 java后端,非常完整的一套交易所,UI前端做的也很漂亮,新增了交易跟单功能,前端pc+wap都是uniapp纯源码,前端源码node_modules环境已经安装好了,拿去直接编译就可以. 后端 前端 免责声明 技术文章仅供参考,任何个人和组织使用网络应当遵守宪法法律,遵守公共…...

基于SpringBoot+Vue+MySQL的个性化电影推荐
系统展示 用户前台界面 管理员后台界面 系统背景 随着在线影视平台的迅猛发展,用户对个性化电影推荐的需求日益增长。传统的电影推荐系统往往基于简单的热门排行或分类筛选,难以满足用户的个性化需求。因此,开发一个基于SpringBootVueMySQL的…...
ASP.NET MVC-异步发送post请求+文件下载
环境: win10, .NET 6.0 前端向后台传递string型变量 前端: function PasteSubmit() {// 获取某个input的值var inName document.getElementById("xx").value;// 获取某个元素的属性值var inSeq document.getElementById("xxx").g…...

Unity 2D RPG Kit 学习笔记
学习资料: B站教学视频:https://www.bilibili.com/video/BV1dC4y1o7A5?p1&vd_source707ec8983cc32e6e065d5496a7f79ee6 2D RPG Kit Documentation.pdf文档 1、2D RPG Kit Documentation文档 1.1、Scenes/TitleScreen 开始菜单工程 1.2、https://it…...
联想天逸100使用笔记
文章目录 配置整理过程锁定功能键怎么弄? 翻出好多年不用的老电脑,饱受折磨,做个笔记。 之前不是我在使用,本身配置就不高,还被装了各种流氓软件,卡的几乎动不了。 配置 老电脑配置不行: i3 5005U 4G内存…...
【AI知识点】嵌入向量(Embedding Vector)
嵌入向量(Embedding Vector)是通过嵌入函数(Embedding Function)将复杂、高维或稀疏数据(如文本、图像、分类特征等)映射到低维、稠密空间中表示的向量。这种向量表示保留了原始数据的语义或结构信息&#…...
github命令行管理工具推荐
GitHub 管理工具推荐 背景 在使用 GitHub 管理仓库时,需要在 Web 端创建远程仓库,在本地创建本地仓库,然后再用 git remote add origin url 进行关联。这个过程相对繁琐,而且还有优化的空间。如果频繁创建仓库,就更能…...

【React】react项目中的redux使用
1. store目录结构设计 2. react组件中使用store中的数据——useSelector 3. react组件中修改store中的数据——useDispatch 4. 示例 react-basic\src\store\moduels\counterStore.js import { createSlice } from reduxjs/toolkitconst counterStore createSlice({name: cou…...
AJAX JSON 实例
AJAX JSON 实例 引言 AJAX(Asynchronous JavaScript and XML)和JSON(JavaScript Object Notation)是现代Web开发中常用的技术。AJAX允许在不重新加载整个页面的情况下,与服务器交换数据和更新部分网页内容。JSON是一种轻量级的数据交换格式,易于人阅读和编写,同时也易…...
java8:hutool:httputil.post读取配置项中的url
如果HttpUtil.post是静态方法,无法直接访问非静态的Value注入的属性。有以下几种解决办法: 构造函数注入 1. 首先将配置项的值通过Value注入到类的成员变量,然后在构造函数中将这个值传递给一个静态变量。 import org.springframework.bean…...
Springboot结合RabbitMQ
pom.xml <!--AMQP依赖,包含RabbitMQ--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId></dependency>application.yaml spring:rabbitmq:host: 127.0.0.1u…...

UNIAPP 动态菜单实现方法
1. 封装tabbar组件,组件UI使用uview的tabbar allList 定义出全部的菜单 list 定义当前用户能看到的菜单使用 u-tabbar 渲染出来 list 2. 权限判断处理 3. 使用方式 在 tab 页,底部放入该 tab 组件,并设置当前回显的页面,这里使用…...
windows C++-使用任务和 XML HTTP 请求进行连接(一)
本文会演示如何将 IXMLHTTPRequest2 和 IXMLHTTPRequest2Callback 接口与任务结合使用,以将 HTTP GET 和 POST 请求发送至通用 Windows 平台 (UWP) 应用中的 Web 服务。 通过将 IXMLHTTPRequest2 与任务组合在一起,你可以编写通过其他任务编写的代码。 例…...

HTB:Oopsie[WriteUP]
目录 连接至HTB服务器并开启靶机 1.With what kind of tool can intercept web traffic? 2.What is the path to the directory on the webserver that returns a login page? 3.What can be modified in Firefox to get access to the upload page? 4.What is the acc…...
【JAVA高级】如何使用Redis加锁和解锁(一)、Lua脚本执行原理及流程
文章目录 加锁方法一:使用SETNX命令结合EXPIRE命令方法二:使用SET命令的扩展参数(NX和PX)方法三:使用Lua脚本 解锁方法一:简单删除key方法二:使用Lua脚本验证后删除key Lua脚本的执行原理&#…...
2024年使用宝塔面板轻松部署Java Web
以下是2024年最新图形化部署Java Web项目到CentOS系统的手把手教程: 一、准备工作 确保服务器环境:确保你的服务器已经安装了CentOS 7操作系统,并且已经安装了宝塔面板。如果还没有安装,可以参考之前的教程进行安装。下载Java W…...

闯关训练一:Linux基础
闯关任务:完成SSH连接与端口映射并运行hello_world.py 1.创建开发机 2.SSH连接 3. VS-Code 连接 选择 Linux 平台 ,输入密码 ,选择进入文件夹 4.端口映射 按照下文安装Docs pip install gradio 运行server.py import gradio as grdef …...

鸿蒙NEXT开发-ArkTS(基于最新api12稳定版)
注意:博主有个鸿蒙专栏,里面从上到下有关于鸿蒙next的教学文档,大家感兴趣可以学习下 如果大家觉得博主文章写的好的话,可以点下关注,博主会一直更新鸿蒙next相关知识 专栏地址: https://blog.csdn.net/qq_56760790/…...
laravel延迟队列 取消未支付超时订单订单
1:生成待支付订单时,调用延迟队列 超过十五分钟未支付自动取消 use App\Jobs\endTask; use Illuminate\Support\Carbon; $resPost1 array("act" > "cy_order_cancel", "id" > $id); endTask::dispatch($resPos…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...

DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...