力扣(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…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...

【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...