刷题DAY38 | LeetCode 509-斐波那契数 70-爬楼梯 746-使用最小花费爬楼梯
509 斐波那契数(easy)
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n ,请计算 F(n) 。
思路:动态规划
代码实现1:
class Solution {
public:int fib(int N) {if (N <= 1) return N;vector<int> dp(N + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[N];}
};
- 时间复杂度:O(n)
- 空间复杂度:O(n)
代码实现2:
class Solution {
public:int fib(int N) {if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
- 时间复杂度:O(n)
- 空间复杂度:O(1)
详细解析:
思路视频
代码实现文章
70 爬楼梯(easy)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
思路:动态规划法
代码实现1:
// 版本一
class Solution {
public:int climbStairs(int n) {if (n <= 1) return n; // 因为下面直接对dp[2]操作了,防止空指针vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) { // 注意i是从3开始的dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};
- 时间复杂度:O(n)
- 空间复杂度:O(n)
代码实现2:
// 版本二
class Solution {
public:int climbStairs(int n) {if (n <= 1) return n;int dp[3];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {int sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
};
- 时间复杂度:O(n)
- 空间复杂度:O(1)
详细解析:
思路视频
代码实现文章
746 使用最小花费爬楼梯(easy)
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
思路:动态规划
代码实现1:
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0; // 默认第一步都是不花费体力的dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.size()];}
};
- 时间复杂度:O(n)
- 空间复杂度:O(n)
代码实现2:
// 版本二
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int dp0 = 0;int dp1 = 0;for (int i = 2; i <= cost.size(); i++) {int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);dp0 = dp1; // 记录一下前两位dp1 = dpi;}return dp1;}
};
- 时间复杂度:O(n)
- 空间复杂度:O(1)
详细解析:
思路视频
代码实现文章
相关文章:
刷题DAY38 | LeetCode 509-斐波那契数 70-爬楼梯 746-使用最小花费爬楼梯
509 斐波那契数(easy) 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) 0,F(1) 1 F(n) F(n - 1)…...
蓝桥杯-卡片换位
solution 有一个测试点没有空格,要特别处理,否则会有一个测试点运行错误! 还有输入数据的规模在变,小心顺手敲错了边界条件 #include<iostream> #include<string> #include<queue> #include<map> #incl…...
Unity 布局控制器Content Size Fitter
Content Size Fitter是Unity中的一种布局控制器组件,用于根据其内容的大小来调整包含它的UI元素的大小。换句话来说就是,Content Size Fitter可以根据UI元素内部内容的大小,自动调整UI元素的大小,以确保内容能够正确显示。 如下图…...
Python的面向对象、封装、继承、多态相关的定义,用法,意义
面向对象编程(OOP)是一种编程范式,它使用对象的概念来模拟现实世界的实体,并通过类(Class)来创建这些实体的蓝图。OOP的核心概念包括封装、继承和多态。 Python中的面向对象编程 在Python中,一…...
Elasticsearch 向量搜索
目标记录 ["你好,我的爱人","你好,我的爱妻","你好,我的病人","世界真美丽"] 搜索词 爱人 预期返回 ["你好,我的爱人","你好,我的爱妻"] 示例代码…...
2024蓝桥杯每日一题(背包)
备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一:货币系统 试题二:01背包问题 试题三:完全背包问题 试题一:货币系统 【题目描述】 给定 V 种货币(单位:元),每…...
Redis桌面客户端
3.4.Redis桌面客户端 安装完成Redis,我们就可以操作Redis,实现数据的CRUD了。这需要用到Redis客户端,包括: 命令行客户端图形化桌面客户端编程客户端 3.4.1.Redis命令行客户端 Redis安装完成后就自带了命令行客户端࿱…...
让Unity的协程变得简单
作者简介: 高科,先后在 IBM PlatformComputing从事网格计算,淘米网,网易从事游戏服务器开发,拥有丰富的C++,go等语言开发经验,mysql,mongo,redis等数据库,设计模式和网络库开发经验,对战棋类,回合制,moba类页游,手游有丰富的架构设计和开发经验。 (谢谢…...
2.9 Python缩进规则(包含快捷键)
Python缩进规则(包含快捷键) 和其它程序设计语言(如 Java、C 语言)采用大括号“{}”分隔代码块不同,Python采用代码缩进和冒号( : )来区分代码块之间的层次。 在 Python 中,对于类…...
任务记录.
播放器端的解码同步问题 miracast的投屏问题,进行修改的问题。 播放器ffplay命令没有声音的修改问题。 任务:如何将断开连接后在连接发送的数据,两秒后再去显示。 猜测: 一直在监听。断开后要求2秒后的数据再显示。那么也就是认为…...
andv vue 实现多张图片上传
1、提示 注意::: 便利出来的数组 点击保存需要 把 双引号去掉 this.formData.image this.imageUrlList.filter((image) > image ! ) 注意::: 回显的时候需要 再把 双引号加上 …...
使用JMeter+Grafana+Influxdb搭建可视化性能测试监控平台
【背景说明】 使用jmeter进行性能测试时,工具自带的查看结果方式往往不够直观和明了,所以我们需要搭建一个可视化监控平台来完成结果监控,这里我们采用三种JMeterGrafanaInfluxdb的方法来完成平台搭建 【实现原理】 通过influxdb数据库存储…...
django模板下,vue的使用(前后端不分离)
目录 关于djangovue的结合使用一、在你的templates中引入vue.js二、关于vue与django模板变量的冲突问题三、示例结语 关于djangovue的结合使用 网上的相关教程基本上都是部署node.js,npm安装vue,生成vue项目,然后将vue项目部署至django,这些…...
python笔记(7)List(列表)
目录 创建列表 取列表中的值 更新列表 删除元素 脚本操作符 嵌套列表 Python列表函数&方法 创建列表 创建一个列表(List)用方括号[]括起来就可以,数据项之间用逗号作为分隔符,数据项可以是字符串,数字,甚至…...
java 抠取红色印章(透明背景)
一个亲戚让我帮他把照片里的红色印章抠出来,,,记录下处理过程,代码如下,可直接用: public static void signatureProcess(String sourceImagePath, String targetImagePath) {Graphics2D graphics2D null…...
CSS及javascript
一、CSS简介 css是一门语言,用于控制网页的表现。 cascading style sheet:层叠样式表 二、css的导入方式 css代码与html代码的结合方式 (1)css导入html有三种方式: 1.内联样式:<div style"color:red&quo…...
LeetCode 1997.访问完所有房间的第一天:动态规划(DP)——4行主要代码(不需要什么前缀和)
【LetMeFly】1997.访问完所有房间的第一天:动态规划(DP)——4行主要代码(不需要什么前缀和) 力扣题目链接:https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/ 你需要访问 n 个房间,房间从 0 到 n - 1 编号。同…...
BootsJS上新!一个库解决大部分难题!
不知不觉距离第一次发文章介绍自己写的库BootsJS已经过去一个月了,这个月里收到了许许多多JYM的反馈与建议,自己也再一次对BootsJS进行了改进与完善,又一次增加了很多功能,为此我想应该给JYM们汇报汇报这个月的工作进展。 BootJS仓…...
智慧公厕,让数据和技术更好服务社会生活
智慧公厕,作为智慧城市建设中不可忽视的一部分,正逐渐受到越来越多人的关注。随着科技的不断进步,智能化公厕已经成为一种趋势,通过数据的流转和技术的整合,为社会生活带来了更好的服务。本文以智慧公厕源头实力厂家广…...
Spark基于DPU Snappy压缩算法的异构加速方案
一、总体介绍 1.1 背景介绍 Apache Spark是专为大规模数据计算而设计的快速通用的计算引擎,是一种与 Hadoop 相似的开源集群计算环境,但是两者之间还存在一些不同之处,这些不同之处使 Spark 在某些工作负载方面表现得更加优越。换句话说&am…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...
