leetcode 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,并完成了你计划的每一天旅行。
示例 2:
输入:days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出:17
解释:
例如,这里有一种购买通行证的方法,可以让你完成你的旅行计划:
在第 1 天,你花了 costs[2] = $15 买了一张为期 30 天的通行证,它将在第 1, 2, …, 30 天生效。
在第 31 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 31 天生效。
你总共花了 $17,并完成了你计划的每一天旅行。
题目链接
提示:
1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000
思路,定义 dp[i] 为到第 i 天的最小 cost,则有,如果 i 不在 days 里面 dp[i] = dp[i-1], 如果 i 在 days 里面 dp[i] = min(dp[i-1]+costs[0], dp[i-7]+costs[1], dp[i-30]+costs[30])
class Solution:def mincostTickets(self, days: List[int], costs: List[int]) -> int:## dp[i] 表示到第 i 天 需要的最少 costINT_MAX = pow(2, 31)-1dp = [INT_MAX for i in range(days[-1]+1)]dp[0] = 0index = 0for i in range(1, len(dp)):if i == days[index]:c1 = dp[i-1] + costs[0]c7 = dp[i-7]+costs[1] if i>=7 else costs[1]c30 = dp[i-30]+costs[2] if i>=30 else costs[2]dp[i] = min(c1, c7, c30)index += 1else:dp[i] = dp[i-1]return dp[-1]相关文章:
leetcode 983. 最低票价
在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车票有 三种不同的销售方式 : 一张 为期一天 的通行证售价为 costs[0] …...
七种遍历Map的方法
七种遍历Map的方法 import java.util.HashMap; import java.util.Iterator; import java.util.Map;public class Wan {public static void main(String[] args) {Map<String,String> dataMap new HashMap<>();dataMap.put("A","Abb");dataMap…...
Android性能优化—内存优化
一、App内存组成以及管理 Android 给每个 App 分配一个 VM ,让App运行在 dalvik 上,这样即使 App 崩溃也不会影响到系统。系统给 VM 分配了一定的内存大小, App 可以申请使用的内存大小不能超过此硬性逻辑限制,就算物理内存富余&…...
Python自动计算Excel数据指定范围内的区间最大值
本文介绍基于Python语言,基于Excel表格文件内某一列的数据,计算这一列数据在每一个指定数量的行的范围内(例如每一个4行的范围内)的区间最大值的方法。 已知我们现有一个.csv格式的Excel表格文件,其中有一列数据&#…...
FTP文件传输协议
FTP文件传输协议 介绍 将某台计算机中的文件通过网络传送到可能相距很远的另一台计算机中,是一项基本的网络应用,即文件传送文件传输协议(File Transfer Protocol)是因特网上使用得最广泛的文件传输协议 FTP提供交互式访问,允许客户指明文件…...
运维高级--tomcat和jpress
1. 简述静态网页和动态网页的区别。 静态网页:事先创建好的网页,通常通过HTML、CSS和JavaScript等静态文件组成,不需要和服务器进行交互,加载速度快 动态网页:根据用户需求动态生成网页,动态网页通常使用…...
【LeetCode】141. 环形链表 进阶题142. 环形链表 II
141. 环形链表 这道题还是用经典的快慢指针法来做。每次让快的指针走两步,慢的走一步。如果有环,则绝对会在环内的某一节点相遇。思想跟物理知识有点关系,如果有环,则在相对运动过程中,可以相当于慢指针静止࿰…...
MySQL索引1——基本概念与索引结构(B树、R树、Hash等)
目录 索引(INDEX)基本概念 索引结构分类 BTree树索引结构 Hash索引结构 Full-Text索引 R-Tree索引 索引(INDEX)基本概念 什么是索引 索引是帮助MySQL高效获取数据的有序数据结构 为数据库表中的某些列创建索引,就是对数据库表中某些列的值通过不同的数据结…...
TikTok数据分析 | 用好超店有数,生意增长快人一步
TikTok在东南亚崛起之快令人叹服。 在东南亚第一大经济体印度尼西亚,超过200万小商家入驻了TikTok的电商平台; TikTok Shop 以6.9亿美元的收入市场份额超越Lazada成为越南第二大电商平台; 2023年泰国TikTok Shop的销售额一路猛涨ÿ…...
从零开始学Docker(三):DockerFile镜像定制
宿主机环境:RockyLinux 9 前言,定制docker镜像的方式有两种: 手动修改容器内容,然后docker commit提交容器为新的镜像通过在dockerfile中定义一系列的命令和参数构成的脚本,然后这些命令应用于基础镜像,依…...
【Linux】 UDP网络套接字编程
🍎作者:阿润菜菜 📖专栏:Linux系统网络编程 文章目录 一、网络通信的本质(port标识的进程间通信)二、传输层协议UDP/TCP认识传输层协议UDP/TCP网络字节序问题(规定大端) 三、socket编…...
《golang设计模式》第一部分·创建型模式-05-工厂方法模式(Factory Method)
文章目录 1 概述2.1 角色2.2 类图 2 代码示例2. 1 设计2.2 代码2.3 类图 3. 简单工厂3.1 角色3.2 类图3.3 代码示例3.3.1 设计3.3.2 代码3.3.3 类图 1 概述 工厂方法类定义产品对象创建接口,但由子类实现具体产品对象的创建。 2.1 角色 Product(抽象产…...
Kubernetes 概述
1、K8S 是什么? K8S 的全称为 Kubernetes (K12345678S) 作用 用于自动部署、扩展和管理“容器化(containerized)应用程序”的开源系统。 可以理解成 K8S 是负责自动化运维管理多个容器化程序(比如 Docker)的集群&#…...
Electron + Vue3 + Vite + TS 构建桌面应用
之前是使用React、Electron、TS和webpack来构建桌面应用的。虽然功能齐全,但是打包等等开发的体验不太理想,总感觉太慢了。作为一个开发者,我们总是希望,执行构建命令后,可以快速打包或者启动本地应用,且通过更少的配置,来完成开发体验。 现在的vite已经得到广泛的应用…...
springboot访问请求404的原因
是记录,可能出现错误 可能出现的原因 1.你请求的URL路径不对,比如说你请求的路径是/usr/list,GET方法,但是你UserController上面的RequestMapping是这个样子:RequestMapping(“user”),有可能哈 2.前端的请求时GET方法,后端对应的处理函数的方…...
网络安全零基础该如何自学?
一、为什么选择网络安全? 这几年随着我国《国家网络空间安全战略》《网络安全法》《网络安全等级保护2.0》等一系列政策/法规/标准的持续落地,网络安全行业地位、薪资随之水涨船高。 未来3-5年,是安全行业的黄金发展期,提前踏入…...
Git(丢失stash数据恢复)
在这里总结一下昨天遇到的问题,我本想将本地代码push到远端仓库,依次运行了以下命令 git init //初始化 git add . //将本地代码添加到暂存区 git commit -m 注释 //将暂存区内容添加到本地仓库中。 结果这时发生了代码冲突,我的代码全没了&a…...
Maven依赖管理
依赖特性: 1、依赖配置 2、依赖传递 3、可选依赖 4、排除依赖 5、依赖范围...
【电网技术复现】考虑实时市场联动的电力零售商鲁棒定价策略(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
R语言中数据重塑(长宽表的转化)
学习笔记,仅供学习使用。 目录 1-什么是整洁的数据? 2-宽表变成长表 示例1: 示例2: 示例3: 3-长表变宽表 示例1: 示例2: 1-什么是整洁的数据? 按照Hadley的表述…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...
自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...
