力扣(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…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...

Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...