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

刷题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 斐波那契数&#xff08;easy&#xff09; 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n) F(n - 1)…...

蓝桥杯-卡片换位

solution 有一个测试点没有空格&#xff0c;要特别处理&#xff0c;否则会有一个测试点运行错误&#xff01; 还有输入数据的规模在变&#xff0c;小心顺手敲错了边界条件 #include<iostream> #include<string> #include<queue> #include<map> #incl…...

Unity 布局控制器Content Size Fitter

Content Size Fitter是Unity中的一种布局控制器组件&#xff0c;用于根据其内容的大小来调整包含它的UI元素的大小。换句话来说就是&#xff0c;Content Size Fitter可以根据UI元素内部内容的大小&#xff0c;自动调整UI元素的大小&#xff0c;以确保内容能够正确显示。 如下图…...

Python的面向对象、封装、继承、多态相关的定义,用法,意义

面向对象编程&#xff08;OOP&#xff09;是一种编程范式&#xff0c;它使用对象的概念来模拟现实世界的实体&#xff0c;并通过类&#xff08;Class&#xff09;来创建这些实体的蓝图。OOP的核心概念包括封装、继承和多态。 Python中的面向对象编程 在Python中&#xff0c;一…...

Elasticsearch 向量搜索

目标记录 ["你好&#xff0c;我的爱人","你好&#xff0c;我的爱妻","你好&#xff0c;我的病人","世界真美丽"] 搜索词 爱人 预期返回 ["你好&#xff0c;我的爱人","你好&#xff0c;我的爱妻"] 示例代码…...

2024蓝桥杯每日一题(背包)

备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一&#xff1a;货币系统 试题二&#xff1a;01背包问题 试题三&#xff1a;完全背包问题 试题一&#xff1a;货币系统 【题目描述】 给定 V 种货币&#xff08;单位&#xff1a;元&#xff09;&#xff0c;每…...

Redis桌面客户端

3.4.Redis桌面客户端 安装完成Redis&#xff0c;我们就可以操作Redis&#xff0c;实现数据的CRUD了。这需要用到Redis客户端&#xff0c;包括&#xff1a; 命令行客户端图形化桌面客户端编程客户端 3.4.1.Redis命令行客户端 Redis安装完成后就自带了命令行客户端&#xff1…...

让Unity的协程变得简单

作者简介: 高科,先后在 IBM PlatformComputing从事网格计算,淘米网,网易从事游戏服务器开发,拥有丰富的C++,go等语言开发经验,mysql,mongo,redis等数据库,设计模式和网络库开发经验,对战棋类,回合制,moba类页游,手游有丰富的架构设计和开发经验。 (谢谢…...

2.9 Python缩进规则(包含快捷键)

Python缩进规则&#xff08;包含快捷键&#xff09; 和其它程序设计语言&#xff08;如 Java、C 语言&#xff09;采用大括号“{}”分隔代码块不同&#xff0c;Python采用代码缩进和冒号&#xff08; : &#xff09;来区分代码块之间的层次。 在 Python 中&#xff0c;对于类…...

任务记录.

播放器端的解码同步问题 miracast的投屏问题&#xff0c;进行修改的问题。 播放器ffplay命令没有声音的修改问题。 任务&#xff1a;如何将断开连接后在连接发送的数据&#xff0c;两秒后再去显示。 猜测&#xff1a; 一直在监听。断开后要求2秒后的数据再显示。那么也就是认为…...

andv vue 实现多张图片上传

1、提示 注意&#xff1a;&#xff1a;&#xff1a; 便利出来的数组 点击保存需要 把 双引号去掉 this.formData.image this.imageUrlList.filter((image) > image ! ) 注意&#xff1a;&#xff1a;&#xff1a; 回显的时候需要 再把 双引号加上 …...

使用JMeter+Grafana+Influxdb搭建可视化性能测试监控平台

【背景说明】 使用jmeter进行性能测试时&#xff0c;工具自带的查看结果方式往往不够直观和明了&#xff0c;所以我们需要搭建一个可视化监控平台来完成结果监控&#xff0c;这里我们采用三种JMeterGrafanaInfluxdb的方法来完成平台搭建 【实现原理】 通过influxdb数据库存储…...

django模板下,vue的使用(前后端不分离)

目录 关于djangovue的结合使用一、在你的templates中引入vue.js二、关于vue与django模板变量的冲突问题三、示例结语 关于djangovue的结合使用 网上的相关教程基本上都是部署node.js,npm安装vue&#xff0c;生成vue项目&#xff0c;然后将vue项目部署至django&#xff0c;这些…...

python笔记(7)List(列表)

目录 创建列表 取列表中的值 更新列表 删除元素 脚本操作符 嵌套列表 Python列表函数&方法 创建列表 创建一个列表&#xff08;List)用方括号[]括起来就可以&#xff0c;数据项之间用逗号作为分隔符&#xff0c;数据项可以是字符串&#xff0c;数字&#xff0c;甚至…...

java 抠取红色印章(透明背景)

一个亲戚让我帮他把照片里的红色印章抠出来&#xff0c;&#xff0c;&#xff0c;记录下处理过程&#xff0c;代码如下&#xff0c;可直接用&#xff1a; public static void signatureProcess(String sourceImagePath, String targetImagePath) {Graphics2D graphics2D null…...

CSS及javascript

一、CSS简介 css是一门语言&#xff0c;用于控制网页的表现。 cascading style sheet:层叠样式表 二、css的导入方式 css代码与html代码的结合方式 &#xff08;1&#xff09;css导入html有三种方式&#xff1a; 1.内联样式&#xff1a;<div style"color:red&quo…...

LeetCode 1997.访问完所有房间的第一天:动态规划(DP)——4行主要代码(不需要什么前缀和)

【LetMeFly】1997.访问完所有房间的第一天&#xff1a;动态规划(DP)——4行主要代码(不需要什么前缀和) 力扣题目链接&#xff1a;https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/ 你需要访问 n 个房间&#xff0c;房间从 0 到 n - 1 编号。同…...

BootsJS上新!一个库解决大部分难题!

不知不觉距离第一次发文章介绍自己写的库BootsJS已经过去一个月了&#xff0c;这个月里收到了许许多多JYM的反馈与建议&#xff0c;自己也再一次对BootsJS进行了改进与完善&#xff0c;又一次增加了很多功能&#xff0c;为此我想应该给JYM们汇报汇报这个月的工作进展。 BootJS仓…...

智慧公厕,让数据和技术更好服务社会生活

智慧公厕&#xff0c;作为智慧城市建设中不可忽视的一部分&#xff0c;正逐渐受到越来越多人的关注。随着科技的不断进步&#xff0c;智能化公厕已经成为一种趋势&#xff0c;通过数据的流转和技术的整合&#xff0c;为社会生活带来了更好的服务。本文以智慧公厕源头实力厂家广…...

Spark基于DPU Snappy压缩算法的异构加速方案

一、总体介绍 1.1 背景介绍 Apache Spark是专为大规模数据计算而设计的快速通用的计算引擎&#xff0c;是一种与 Hadoop 相似的开源集群计算环境&#xff0c;但是两者之间还存在一些不同之处&#xff0c;这些不同之处使 Spark 在某些工作负载方面表现得更加优越。换句话说&am…...

s2-pro部署实操:CSDN平台GPU资源监控与s2-pro服务性能关联分析

s2-pro部署实操&#xff1a;CSDN平台GPU资源监控与s2-pro服务性能关联分析 1. 专业语音合成工具s2-pro简介 s2-pro是Fish Audio开源的专业级语音合成模型镜像&#xff0c;它能够将文本转换为自然流畅的语音&#xff0c;并支持通过参考音频来复用特定音色。这个工具特别适合需…...

如何快速掌握FModel:解锁虚幻引擎游戏资源的完整实战指南 [特殊字符]

如何快速掌握FModel&#xff1a;解锁虚幻引擎游戏资源的完整实战指南 &#x1f3ae; 【免费下载链接】FModel Unreal Engine Archives Explorer 项目地址: https://gitcode.com/gh_mirrors/fm/FModel FModel是一款功能强大的虚幻引擎游戏资源解析工具&#xff0c;能够帮…...

Biolaminin 层粘连蛋白(LN521)在干细胞培养中的作用与应用解析【曼博生物官方代理BioLamina】

摘要&#xff1a;人类重组层粘连蛋白&#xff08;Laminin&#xff09;&#xff0c;尤其是LN521亚型&#xff0c;在多能干细胞培养中具有重要作用。本文从细胞微环境、培养体系及应用场景角度&#xff0c;对其在干细胞研究与转化中的价值进行系统梳理。 关键词&#xff1a;LN521…...

SDMatte在电商场景落地:商品主图自动去背景+透明PNG生成完整工作流

SDMatte在电商场景落地&#xff1a;商品主图自动去背景透明PNG生成完整工作流 1. 电商场景中的图像处理痛点 在电商运营中&#xff0c;商品主图的质量直接影响转化率。传统处理方式面临三大难题&#xff1a; 人工成本高&#xff1a;专业设计师处理一张图平均耗时15-30分钟边…...

魔兽世界API开发助手:从新手到专家的全流程解决方案

魔兽世界API开发助手&#xff1a;从新手到专家的全流程解决方案 【免费下载链接】wow_api Documents of wow API -- 魔兽世界API资料以及宏工具 项目地址: https://gitcode.com/gh_mirrors/wo/wow_api 价值定位&#xff1a;如何避免90%的插件开发陷阱&#xff1f; 在魔…...

从 0 开始讲透 C++ Lambda(对标 Java)

在写 C 多线程或 STL 时&#xff0c;经常会看到这样的代码&#xff1a;std::thread t([]{ std::cout << "Hello C Thread\n"; });很多人第一反应&#xff1a;这 [] 是什么&#xff1f;为什么和 Java 不一样&#xff1f;一、先给结论&#xff08;先建立整体认知…...

免环境配置:Qwen-Image定制镜像让4090D显卡快速跑通视觉语言模型

免环境配置&#xff1a;Qwen-Image定制镜像让4090D显卡快速跑通视觉语言模型 1. 引言 1.1 视觉语言模型的应用价值 在当今AI技术快速发展的背景下&#xff0c;视觉语言模型(VLM)已成为连接计算机视觉与自然语言处理的桥梁。这类模型能够理解图像内容并生成相关文本描述&…...

HFSS建模进阶:如何高效使用布尔运算和局部坐标系(实战案例解析)

HFSS建模进阶&#xff1a;布尔运算与局部坐标系的高效实战指南 在微波器件和天线设计的数字世界里&#xff0c;精确的三维建模往往是成功仿真的第一步。当您已经掌握了HFSS的基础建模操作后&#xff0c;如何将建模效率提升到专业水平&#xff1f;本文将带您深入探索两个常被忽视…...

硬件加速对比:Qwen3-32B镜像在RTX4090D与A100上的OpenClaw表现

硬件加速对比&#xff1a;Qwen3-32B镜像在RTX4090D与A100上的OpenClaw表现 1. 测试背景与实验设计 最近在部署OpenClaw自动化工作流时&#xff0c;遇到了一个实际需求&#xff1a;如何为本地AI智能体选择最具性价比的GPU硬件&#xff1f;我的工作流主要依赖Qwen3-32B模型进行…...

LumiPixel优化升级:如何利用Z-Image模型生成更细腻的像素人像

LumiPixel优化升级&#xff1a;如何利用Z-Image模型生成更细腻的像素人像 1. 引言&#xff1a;像素艺术的复兴与挑战 像素艺术作为一种独特的数字艺术形式&#xff0c;近年来在游戏、NFT和数字设计领域迎来复兴。然而传统像素创作面临两大核心挑战&#xff1a; 细节表现力不…...