当前位置: 首页 > 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…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了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 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; 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 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

【笔记】WSL 中 Rust 安装与测试完整记录

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