leetcode_动态规划/递归 70. 爬楼梯
70. 爬楼梯
-
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
-
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
-
思路:
- 考虑: 假设现在已经爬到了某一阶台阶,那是如何到达这里的呢?可能是从前一阶台阶爬上来的,也可能是从前两阶台阶爬上来的。也就是说,从第 i 阶楼梯,可以从第 i - 1 或者 i - 2 阶楼梯爬上来。因此,有一个递推公式:d[i] = d[i-1] + d[i-2]
1. 动态规划
# 1. 动态规划
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n < 1:return 0if n == 1:return 1elif n == 2:return 2d = [0] * (n + 1) # 初始化列表长度为 n + 1, 所有元素的值为 0, 用来存储每个台阶的爬法数d[1] = 1 # 第 1 阶只有 1 种方式d[2] = 2 # 第 2 阶有 2 种方式# 从第 3 阶开始,根据递推公式计算每个台阶的爬法数for i in range(3, n + 1):d[i] = d[i - 1] + d[i - 2]# 返回到达第 n 阶的方法数return d[n]
- 时间复杂度: O(n)
- 空间复杂度: O(n)
空间优化版本
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n < 1:return 0if n == 1:return 1elif n == 2:return 2# 使用两个变量来存储前两阶的爬法数prev1, prev2 = 2, 1 # prev1 是 d[i-1], prev2 是 d[i-2]for i in range(3, n + 1):current = prev1 + prev2prev2 = prev1prev1 = current# 返回最终的结果return prev1
- 时间复杂度: O(n)
- 空间复杂度: O(1)
2. 递归法
# 2. 递归(ps: 递归法在leetcode中运行会超时)
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n <= 1:return 1return self.climbStairs(n-1) + self.climbStairs(n-2)
- 时间复杂度: O(2^n),递归调用的过程形成了一个类似于树的结构,每一层都会有两个递归分支,导致时间复杂度呈指数级增长。总的递归调用数大约为 2^n,因此时间复杂度是 O(2^n)。
- 空间复杂度: O(n),递归调用会在系统栈中占用空间,每一次递归都会添加一个新的栈帧,直到到达基准情况(n <= 1)。最深的递归调用栈的深度为 n(因为递归每次减少 1 或 2),所以空间复杂度是 O(n)。
相关文章:
leetcode_动态规划/递归 70. 爬楼梯
70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 思路: 考虑: 假设现在已经爬到了某一阶台阶,那是如何到达这里的呢?可能是从前一阶台阶爬上来的&am…...
基于Rook的Ceph云原生存储部署与实践指南(上)
#作者:任少近 文章目录 1 Ceph环境准备2 rook部署ceph群集2.1 Rook 帮助地址2.2 安装ceph2.3 获取csi镜像2.4 Master参加到osd2.5 设置默认存储 3 Rook部署云原生RBD块存储3.1 部署storageclass资源3.2 部署WordPress使用RBD3.3 WordPress访问 4 Rook部署云原生RGW…...
C++ Qt常见面试题(4):Qt事件过滤器
在 Qt 中,事件过滤器(Event Filter)提供了一种机制,可以拦截并处理对象的事件(如鼠标事件、键盘事件等),在事件到达目标对象之前对其进行预处理。事件过滤器通常用于以下场景: 捕获和处理特定的事件(如鼠标点击、按键等);对事件进行筛选或修改;实现全局的事件监听功…...
regionserver实例僵住问题分析
问题现象: 应用提交超时,发现regionserver实例异常。hbase原生页面这个实例dead,业务连接到这个rs的进程超时8个regionserver实例。 D08在18:30分后显示warning,应用提交任务到这个rs节点超时,hbase控制台不显示d08的rs信息了。19:30在页面停止rs实例失败,然后kill进程…...
服务器离线部署DeepSeek
目标 本次部署的目标是在本地服务器上部署DeepSeek。但是该服务不能连接外网,因此只能使用离线部署的方式。为了一次完成部署。现在云服务器上进行尝试。 云服务器部署尝试 云服务器配置 CentOS72080Ti 11GB 安装准备 1、上传iso并配置为本地yum源 安装前先将…...
QT mac系统下qml实现的菜单栏,标准快捷键Delete无作用或失灵的处理
一.在mac系统下,QT官方提供的删除快捷键无作用。 1.下面这一段代码,最后一个menuItem采用的是QT自带的标准快捷键,但是在使用的过程中,快捷键无响应。大家可以将代码带入简单的demo尝试一下: MenuBar {id: rootMenu {id: editMenutitle: TransText.titleBar_EditMenuItem…...
redis序列化设置
redis序列化设置 redis序列化设置序列化对象里有org.joda.time.DateTime1)、报错内容如下2)、解决方案:分别自定义时间的序列化和反序列化,以对象形式关联到redisTemplate redis序列化设置 redis序列化设置,通过自定义…...
浅谈C++/C命名冲突
前言 在这里我会简要地介绍产生命名冲突的原因,和C中处理命名冲突的方法,同时和C语言的解决办法进行比较。 相信你在阅读完之后一定会有收获。对于我们来说,了解编译器的编译链接过程才能更好的理解编译器是如何报错的,更能让我们…...
【语音编解码】常用的基于神经网络的语音编解码方案对比
引言 随着实时通信与多媒体应用的爆炸式增长,传统语音编解码技术正面临带宽效率与音质保真的双重挑战。近年来,基于深度学习的神经编解码器突破性地将端到端架构、动态码率控制与可解释信号处理相结合,在3kbps以下超低码率场景仍能保持自然语…...
PVE 配置显卡直通
博客地址:PVE 配置显卡直通 配置 Device: Dell PowerEdge T630CPU: Intel Xeon E5-2696 v4 x2GPU 1: Matrox Electronics Systems Ltd. G200eR2GPU 2: NVIDIA GeForce GTX 1060 3GBOS: Proxmox VE bookworm 8.3.1 x86_64 注意事项 硬件需支持并在 BIOS 中开启 I…...
Kronecker分解(K-FAC):让自然梯度在深度学习中飞起来
Kronecker分解(K-FAC):让自然梯度在深度学习中飞起来 在深度学习的优化中,自然梯度下降(Natural Gradient Descent)是一个强大的工具,它利用Fisher信息矩阵(FIM)调整梯度…...
ArcGIS Pro技巧实战:高效矢量化天地图地表覆盖图
在地理信息系统(GIS)领域,地表覆盖图的矢量化是一项至关重要的任务。天地图作为中国国家级的地理信息服务平台,提供了丰富且详尽的地表覆盖数据。然而,这些数据通常以栅格格式存在,不利于进行空间分析和数据…...
React + TypeScript 数据模型驱动数据字典生成示例
React TypeScript 数据模型驱动数据字典生成示例 引言:数据字典的工程价值 在现代化全栈开发中,数据字典作为业务实体与数据存储的映射桥梁,直接影响系统可维护性与团队协作效率。传统手动维护字典的方式存在同步成本高和版本管理混乱两大痛…...
道可云人工智能每日资讯|深圳将设立人工智能和机器人产业基金
道可云元宇宙每日简报(2025年2月26日)讯,今日元宇宙新鲜事有: 上海青浦发布国际产业协作元宇宙平台 近日,“2025出海企业与跨境专业服务论坛”在上海青浦区徐泾镇举行。论坛上重磅发布三大全球化服务平台,…...
[2024年下半年架构师考试真题之论文]
2024论文真题试题一(架构) 论面向服务的架构设计 Web service 是一种通过互联网协议(如 HTTP)来提供服务的软件系统,它允许不同的应用程序之间进行交互,而无需考虑它们所使用的操作系统、编程语言或硬件平台。其本质是将应用程序的功能以服务的形式暴露出来,使得其他应…...
神经网络 - 激活函数(Sigmoid 型函数)
激活函数在神经元中非常重要的。为了增强网络的表示能力和学习能力,激活函数需要具备以下几点性质: (1) 连续并可导(允许少数点上不可导)的非线性函数。可导的激活函数可以直接利用数值优化的方法来学习网络参数. (2) 激活函数及其导函数要尽可能的简单࿰…...
阿里云 | 快速在网站上增加一个AI助手
创建智能体应用 如上所示,登录阿里云百炼人工智能业务控制台,创建智能体应用,智能体应用是一个agent,即提供个人或者企业的代理或中间件组件应用,对接阿里云大模型公共平台,为个人或者企业用户提供大模型应…...
【操作系统】处理机调度
处理机调度 一、调度的概念、层次1.1 三个层次1.2 七状态模型 二、调度算法的评价指标2.1 CPU利用率2.2 系统吞吐率2.3 周转时间2.4 等待时间2.5 响应时间 三、进程调度(低级调度)的时机3.1 需要进程调度的情况3.2 不能进程调度的情况3.3 闲逛进程 四、进…...
mysql服务层介绍,NOSQL+SQL接口(nosql介绍),语法分析器,预处理器,优化器(优化的必要性,基于成本的优化器),缓存(弊端)
目录 mysql服务层 介绍 服务管理和公共组件 备份 NOSQL,SQL接口 介绍 nosql Parser模块(语法分析器) 介绍 词法分析 语法分析 示例 预处理器 引入 介绍 优化器 介绍 优化的必要性 基于成本的优化器 缓存 介绍 弊端 mysql服务层 介绍 数据库服务层是整个…...
将DeepSeek接入vscode的N种方法
接入deepseek方法一:cline 步骤1:安装 Visual Studio Code 后,左侧导航栏上点击扩展。 步骤2:搜索 cline,找到插件后点击安装。 步骤3:在大模型下拉菜单中找到deep seek,然后下面的输入框输入你在deepseek申请的api key,就可以用了 让deepseek给我写了一首关于天气的…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
