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

力扣(leetcode)每日一题 983 最低票价 |动态规划

983. 最低票价

题干

在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1365 的整数。

火车票有 三种不同的销售方式

  • 一张 为期一天 的通行证售价为 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. 最低票价 题干 在一个火车旅行很受欢迎的国度&#xff0c;你提前一年计划了一些火车旅行。在接下来的一年里&#xff0c;你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车票有 三种不同的销售方式 &#xff1a; 一张 为期一天 的通…...

【漏洞复现】VEXUS多语言货币交易所存在未授权访问漏洞

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

基于SpringBoot+Vue+MySQL的个性化电影推荐

系统展示 用户前台界面 管理员后台界面 系统背景 随着在线影视平台的迅猛发展&#xff0c;用户对个性化电影推荐的需求日益增长。传统的电影推荐系统往往基于简单的热门排行或分类筛选&#xff0c;难以满足用户的个性化需求。因此&#xff0c;开发一个基于SpringBootVueMySQL的…...

ASP.NET MVC-异步发送post请求+文件下载

环境&#xff1a; win10, .NET 6.0 前端向后台传递string型变量 前端&#xff1a; function PasteSubmit() {// 获取某个input的值var inName document.getElementById("xx").value;// 获取某个元素的属性值var inSeq document.getElementById("xxx").g…...

Unity 2D RPG Kit 学习笔记

学习资料&#xff1a; B站教学视频&#xff1a;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使用笔记

文章目录 配置整理过程锁定功能键怎么弄? 翻出好多年不用的老电脑&#xff0c;饱受折磨&#xff0c;做个笔记。 之前不是我在使用&#xff0c;本身配置就不高&#xff0c;还被装了各种流氓软件&#xff0c;卡的几乎动不了。 配置 老电脑配置不行&#xff1a; i3 5005U 4G内存…...

【AI知识点】嵌入向量(Embedding Vector)

嵌入向量&#xff08;Embedding Vector&#xff09;是通过嵌入函数&#xff08;Embedding Function&#xff09;将复杂、高维或稀疏数据&#xff08;如文本、图像、分类特征等&#xff09;映射到低维、稠密空间中表示的向量。这种向量表示保留了原始数据的语义或结构信息&#…...

github命令行管理工具推荐

GitHub 管理工具推荐 背景 在使用 GitHub 管理仓库时&#xff0c;需要在 Web 端创建远程仓库&#xff0c;在本地创建本地仓库&#xff0c;然后再用 git remote add origin url 进行关联。这个过程相对繁琐&#xff0c;而且还有优化的空间。如果频繁创建仓库&#xff0c;就更能…...

【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是静态方法&#xff0c;无法直接访问非静态的Value注入的属性。有以下几种解决办法&#xff1a; 构造函数注入 1. 首先将配置项的值通过Value注入到类的成员变量&#xff0c;然后在构造函数中将这个值传递给一个静态变量。 import org.springframework.bean…...

Springboot结合RabbitMQ

pom.xml <!--AMQP依赖&#xff0c;包含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组件&#xff0c;组件UI使用uview的tabbar allList 定义出全部的菜单 list 定义当前用户能看到的菜单使用 u-tabbar 渲染出来 list 2. 权限判断处理 3. 使用方式 在 tab 页&#xff0c;底部放入该 tab 组件&#xff0c;并设置当前回显的页面&#xff0c;这里使用…...

windows C++-使用任务和 XML HTTP 请求进行连接(一)

本文会演示如何将 IXMLHTTPRequest2 和 IXMLHTTPRequest2Callback 接口与任务结合使用&#xff0c;以将 HTTP GET 和 POST 请求发送至通用 Windows 平台 (UWP) 应用中的 Web 服务。 通过将 IXMLHTTPRequest2 与任务组合在一起&#xff0c;你可以编写通过其他任务编写的代码。 例…...

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脚本执行原理及流程

文章目录 加锁方法一&#xff1a;使用SETNX命令结合EXPIRE命令方法二&#xff1a;使用SET命令的扩展参数&#xff08;NX和PX&#xff09;方法三&#xff1a;使用Lua脚本 解锁方法一&#xff1a;简单删除key方法二&#xff1a;使用Lua脚本验证后删除key Lua脚本的执行原理&#…...

2024年使用宝塔面板轻松部署Java Web

以下是2024年最新图形化部署Java Web项目到CentOS系统的手把手教程&#xff1a; 一、准备工作 确保服务器环境&#xff1a;确保你的服务器已经安装了CentOS 7操作系统&#xff0c;并且已经安装了宝塔面板。如果还没有安装&#xff0c;可以参考之前的教程进行安装。下载Java W…...

闯关训练一:Linux基础

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

鸿蒙NEXT开发-ArkTS(基于最新api12稳定版)

注意&#xff1a;博主有个鸿蒙专栏&#xff0c;里面从上到下有关于鸿蒙next的教学文档&#xff0c;大家感兴趣可以学习下 如果大家觉得博主文章写的好的话&#xff0c;可以点下关注&#xff0c;博主会一直更新鸿蒙next相关知识 专栏地址: https://blog.csdn.net/qq_56760790/…...

laravel延迟队列 取消未支付超时订单订单

1&#xff1a;生成待支付订单时&#xff0c;调用延迟队列 超过十五分钟未支付自动取消 use App\Jobs\endTask; use Illuminate\Support\Carbon; $resPost1 array("act" > "cy_order_cancel", "id" > $id); endTask::dispatch($resPos…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

DingDing机器人群消息推送

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

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...