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

【LeetCode】每日一题 2024_10_1 最低票价(记忆化搜索/DP)

前言

每天和你一起刷 LeetCode 每日一题~

大家国庆节快乐呀~

LeetCode 启动!

题目:最低票价

代码与解题思路

今天这道题是经典动态规划,我们定义 dfs(i) 表示从第 1 天到 第 i 天的最小花费,然后使用祖传的:从记忆化搜索 -> 动态规划的思路开始解题

记忆化搜索:

func mincostTickets(days []int, costs []int) int {n := days[len(days)-1]needCost := make([]bool, n+1)for _, v := range days { // 记录需要通行证的日子needCost[v] = true}// 记忆化memo := make([]int, n+1)for i := range memo {memo[i] = -1}// i 表示第 1 天到 第 i 天的最小花费var dfs func(int) intdfs = func(i int) (res int) {if i <= 0 { // 不存在的情况就返回 0return 0}// 记忆化操作p := &memo[i]if *p != -1 {return *p}defer func() {*p = res}()if !needCost[i] { // 如果不需要通行证,那就不需要花费res = dfs(i-1)} else { // 选出三种花费中最小的一种res = min(dfs(i-1)+costs[0], dfs(i-7)+costs[1], dfs(i-30)+costs[2])}return res}return dfs(n)
}

记忆化搜索转递推:

func mincostTickets(days []int, costs []int) int {n := days[len(days)-1]needCost := make([]bool, n+1)for _, v := range days {needCost[v] = true}f := make([]int, n+1)for i := 1; i < len(f); i++ {if !needCost[i] {f[i] = f[i-1]} else { f[i] = min(f[i-1]+costs[0], f[max(i-7, 0)]+costs[1], f[max(i-30, 0)]+costs[2])}}return f[n]
}

基本上一比一复刻就可以啦~

有一个需要注意的点,在使用状态转移方程的时候:min(f[i-1]+costs[0], f[max(i-7, 0)]+costs[1], f[max(i-30, 0)]+costs[2]),这里用了 max(i-7, 0) 和 max(i-30, 0),其实就是记忆化搜索中的:

if i <= 0 {return 0
}

如果不存在这种情况,就返回 0,不记入总花费。

视频实况

[【【LeetCode】每日一题 2024_10_1 最低票价(记忆化搜索/DP)】 ]( https://www.bilibili.com/video/BV19CxheNETm/?share_source=copy_web&vd_source=5838aabca6ee756488292563a3936f1d

每天进步一点点

可以和我刷一辈子的每日一题吗?
一题一题,积累起来就是一辈子。

相关文章:

【LeetCode】每日一题 2024_10_1 最低票价(记忆化搜索/DP)

前言 每天和你一起刷 LeetCode 每日一题~ 大家国庆节快乐呀~ LeetCode 启动&#xff01; 题目&#xff1a;最低票价 代码与解题思路 今天这道题是经典动态规划&#xff0c;我们定义 dfs(i) 表示从第 1 天到 第 i 天的最小花费&#xff0c;然后使用祖传的&#xff1a;从记忆…...

[C++] 小游戏 征伐 SLG DNF 0.0.1 版本 zty出品

目录 先赞后看 养成习惯 War and Expedition SLG DNF 0.0.1 version 讲人话就是 图标解释&#xff1a; 绿色代表空地&#xff0c;可通过&#xff0c;对应数值 0 蓝色“~ ”为水&#xff0c;不可通过&#xff0c;对应数值 1 棕色“”为桥梁&#xff0c;可通过&#xff0…...

黑马头条day7-app端文章搜索

今天的内容也只是跑了一下 对于具体的实现掌握的很差 仔细看 es 在微服务学的es使用基本忘光了 这里用起来一点都熟悉 重学&#xff01;&#xff01;&#xff01; kafka异步 文章自动构建索引的时候用到了‘’ mongoDB 用来存储用户的搜索记录 遗忘&#xff08;拦截器 j…...

嵌入式必懂微控制器选型:STM32、ESP32、AVR与PIC的比较分析

目录 1 微控制器基础概述 1.1 微控制器基本概念 1.2 工作原理及架构 1.3 STM32、ESP32、AVR和PIC简介 2 微控制器性能比较分析 2.1 性能比较 2.2 功耗比较 2.3 功耗分析 2.4 外设接口对比 3 应用场景与选择策略 3.1 物联网应用场景 3.2 工业控制场景 3.3 智能家居场…...

Python selenium库学习使用实操二

系列文章目录 Python selenium库学习使用实操 文章目录 系列文章目录前言一、模拟登录二、表单录入 前言 在上一篇文章中&#xff0c;我们完成Selenium环境的搭建&#xff0c;和简单的自动化。今天继续深入学习。今天的目标是完成模拟登录&#xff0c;和表单录入。 一、模拟登…...

基于Hive和Hadoop的电信流量分析系统

本项目是一个基于大数据技术的电信流量分析系统&#xff0c;旨在为用户提供全面的通信数据和深入的流量使用分析。系统采用 Hadoop 平台进行大规模数据存储和处理&#xff0c;利用 MapReduce 进行数据分析和处理&#xff0c;通过 Sqoop 实现数据的导入导出&#xff0c;以 Spark…...

访问docker容器中服务的接口,报错提示net::ERR_CONNECTION_REFUSED

背景 使用httpclient和前端调用docker容器中部署的springboot服务接口,一直连接不上。 报错信息 AxiosError {message: Network Error, name: AxiosError, code: ERR_NETWORK, config: {…}, request: XMLHttpRequest, …} sys.ts:28 POST http://172.33.28.179:8181/sy…...

【mysql相关总结】

mysql相关总结 数据库小的表,全表扫描效率更高&#xff0c;不用建索引。 索引的类型 1.普通索引&#xff1a;基本的索引&#xff0c;没有任何约束限制 2.唯一索引&#xff1a;类似普通索引,有唯一约束性 3.主键索引&#xff1a;特殊的唯一索引,不允许有空值 4.组合索引&#xf…...

uniapp 微信小程序 微信支付

本章的内容我尽量描述的细致一些&#xff0c;哪里看不懂给我评论就可以&#xff0c;我看到进行回复 微信支付大致分为4步&#xff0c;具体看后端设计 1. 获取code 2. 根据code获取openid 3. 根据openid&#xff0c;以及部分订单相关数据&#xff0c;生成prepayId (预支付交易会…...

CSS 效果:实现动态展示双箭头

最近写了一段 CSS 样式&#xff0c;虽然不难&#xff0c;但实现过程比较繁琐。这个效果结合了两个箭头&#xff0c;一个突出&#xff0c;一个内缩&#xff0c;非常适合用于步骤导航或选项卡切换等场景。样式不仅仅是静态的&#xff0c;还可以通过点击 click 或者 hover 事件&am…...

Linux 创建开发用的账户

在Linux系统中&#xff0c;创建一个用于开发的用户账户通常涉及到添加用户、设置密码以及配置适当的权限和环境。这里将详细介绍如何在Linux系统中创建一个新的开发用户账户&#xff0c;包括为其配置sudo权限&#xff0c;使其能够执行需要管理员权限的命令。 步骤 1: 创建用户…...

检查一个CentOS服务器的配置的常用命令

在CentOS系统中&#xff0c;查看服务器配置的常用命令非常丰富&#xff0c;这些命令可以帮助用户快速了解服务器的硬件信息、系统状态以及网络配置等。以下是一些常用的命令及其简要说明&#xff1a; 1. 查看CPU信息 (1) cat /proc/cpuinfo&#xff1a;显示CPU的详细信息&…...

Redis 简单的消息队列

使用redis 进行简单的队列很容易&#xff0c;不需要使用较为复杂的MQ队列&#xff0c;直接使用redis 进行&#xff0c;不过唯一不足的需要自己构造生产者消费者&#xff0c;这里使用while True的方法进行消费者操作 目录 介绍数据类型StringHash 重要命令消息队列 介绍 key-v…...

C++:继承和多态,自定义封装栈,队列

1.栈&#xff1a; stack.cpp #include "stack.h"Stack::Stack():top(nullptr),len(0){} //析构函数 Stack::~Stack() {while(!empty()){pop();} }bool Stack::empty() //判断栈是否为空 {return topnullptr; }int Stack::size()//获取栈的大小 {return len; } //压…...

Python多个set中的交集

Python多个set中的交集 在 Python 中&#xff0c;集合&#xff08;set&#xff09;是一种非常有用的数据结构&#xff0c;它可以存储唯一的元素&#xff0c;并提供了高效的数学集合操作&#xff0c;包括求交集、并集和差集等。本文将重点介绍如何通过多重集合求交集&#xff0…...

百度百科 X-Bk-Token 算法还原

声明 本文章中所有内容仅供学习交流,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关,若有侵权,请私信我立即删除! 文章目录 声明案例地址参数分析X-Bk-Token算法追踪X-Bk-Token后缀算法还原c 值跟踪与算法还原往期逆向文章推荐最近太忙了,博客摆烂了好…...

RUST语言的初印象-从一个模拟登陆谈起-slint+reqwest+aes

本文就一个做了三四天的小程序讲第一次学用RUST的感受&#xff0c;内附代码。 了角语言 从一些渠道听说了R&#xff0c;这个字母挺魔性&#xff0c;那个文章说C和R的团体已经上升到了宗教崇拜的高度&#xff0c;然后&#xff0c;我觉得必 有过人之处&#xff0c;大约10年没碰…...

HBase批量写入优化

HBase批量写入性能优化 对于HBase的批量写入性能优化&#xff0c;可以考虑以下几点&#xff1a; 1.批量写入操作&#xff1a;使用HBasef的批量写入操作可以显著提高性能。将多个写入操作放在一个批次中一起提交。这样可以减少网络通信开销和减少多次写入操作的开销。方法不限。…...

江协科技STM32学习- P19 TIM编码器接口

&#x1f680;write in front&#x1f680; &#x1f50e;大家好&#xff0c;我是黄桃罐头&#xff0c;希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流 &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd;​…...

文件上传、重定向、Gin路由

文件上传 单个文件上传 index.html 文件上传前端页面代码&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><title>index</title> </head> <body> <form action"/upload" method"post"…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...