# 爬楼梯问题:常见数列的解法总结
爬楼梯问题:常见数列的解法总结
在编程中,爬楼梯问题(Climbing Stairs Problem)是一个经典的动态规划问题,常常作为入门学习动态规划和递推的重要例题。这个问题看似简单,但背后包含了多种解决方式,尤其是与 斐波那契数列 和 组合数 等数列的关系。
本文将总结几种常见的数列解法,帮助大家更好地理解爬楼梯问题的多样性和灵活性。
问题描述
假设你正在爬楼梯。每次可以爬 1 或 2 个台阶,求你有多少种不同的方法可以爬到楼顶。
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶:
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶:
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
数列解法概述
爬楼梯问题本质上可以通过不同的数列模型来解决。不同的解法可以使用以下几种常见的数列:
1. 斐波那契数列解法
斐波那契数列是最常见的解法之一。问题的递推关系是:每个台阶有两种选择:
- 从前一个台阶跳 1 个台阶
- 从前两个台阶跳 2 个台阶
所以我们可以得出以下递推公式:
dp[i] = dp[i-1] + dp[i-2]
其中 dp[i]
表示到达第 i
阶的方法数。
代码实现:
class Solution:def climbStairs(self, n: int) -> int:a, b = 1, 1for i in range(n - 1):a, b = b, a + breturn b
解释:
a
和b
分别表示爬到第i-1
阶和第i
阶的方法数。- 每次循环,
b
更新为当前和前一个的和,即b = a + b
。 - 最终,
b
就是爬到第n
阶的方法数。
2. 动态规划解法
通过动态规划,我们可以保存中间结果,避免重复计算。这个方法适用于 n
较大时的优化。
代码实现:
class Solution:def climbStairs(self, n: int) -> int:dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):dp[i] = dp[i-1] + dp[i-2]return dp[n]
解释:
dp[i]
表示到达第i
阶的方法数。- 初始化
dp[0]
和dp[1]
为 1,因为从第 0 阶和第 1 阶都有一种方法。 - 从第 2 阶开始递推,每次累加前两个状态的值。
3. 滚动数组解法
为了进一步优化空间复杂度,我们可以使用滚动数组。只需要保存前两个台阶的结果,即可推算出当前台阶的结果,减少空间消耗。
代码实现:
class Solution:def climbStairs(self, n: int) -> int:a, b = 1, 1for i in range(2, n + 1):a, b = b, a + breturn b
解释:
- 通过两个变量
a
和b
代替整个dp
数组,节省了空间。 - 每次迭代时,更新
a
和b
的值。
4. 数学公式解法(组合数)
爬楼梯问题也可以通过组合数来解决。我们可以将问题转化为选择问题——在 n
个台阶中,有多少种方法选择其中的 k
步为 2 步。
在这种情况下,我们有:
- 选择
k
步 2 台阶,总共走k
步 2 台阶和n - k
步 1 台阶。 - 这个问题可以使用 组合数公式 来计算。
公式为:
C(n, k) = n! / (k! * (n - k)!)
其中 n
是台阶数,k
是选择的 2 台阶的个数。
代码实现:
import mathclass Solution:def climbStairs(self, n: int) -> int:return math.comb(n, n // 2) # 选择 n//2 步为 2 台阶
解释:
- 我们选择
n//2
步作为 2 台阶,总共会有n - n//2
步 1 台阶。 - 使用
math.comb()
来计算组合数,得出可能的路径数。
5. 递归解法
递归解法是最直接的思路,可以通过递归计算出每个台阶的方案数,但其效率较低,适合展示算法的基本思路。由于存在大量的重复计算,递归解法的时间复杂度是指数级的。
代码实现:
class Solution:def climbStairs(self, n: int) -> int:if n <= 2:return nreturn self.climbStairs(n - 1) + self.climbStairs(n - 2)
解释:
- 每次递归都会减去 1 或 2,直到计算到达第 1 或第 2 阶。
- 这种解法可以看作是 暴力解法,时间复杂度高,适合理解递推关系。
总结
爬楼梯问题通过数列的不同解法展现了动态规划、递归和组合数等多种算法技巧。常见的解法有:
- 斐波那契数列:通过递推关系来计算,时间复杂度 O(n)。
- 动态规划:通过存储中间结果避免重复计算,空间复杂度 O(n)。
- 滚动数组:进一步优化空间复杂度,空间复杂度 O(1)。
- 组合数:通过数学公式计算,适用于考虑组合问题。
- 递归:暴力解法,通过递归计算,时间复杂度指数级。
不同解法适用于不同的场景,在面试和实际开发中,可以根据题目的要求选择最合适的解法。
相关文章:
# 爬楼梯问题:常见数列的解法总结
爬楼梯问题:常见数列的解法总结 在编程中,爬楼梯问题(Climbing Stairs Problem)是一个经典的动态规划问题,常常作为入门学习动态规划和递推的重要例题。这个问题看似简单,但背后包含了多种解决方式&#x…...
速通Docker === 常用命令
目录 Docker命令 镜像操作 容器操作 基础操作 启动参数 容器内部操作 打包成指定文件 发布镜像 总结 镜像操作 容器操作 启动容器参数 容器内部操作 打包镜像 启动指定镜像的容器 发布镜像 Docker命令 启动一个nginx,并将它的首页改为自己的页面,发布…...
AWS S3 跨账户访问 Cross Account Access
进入S3对应的存储桶,上面选项选权限,存储桶策略 -- 编辑,输入对应的policy。 完全控制,包含上传删除权限,policy如下: {"Version": "2012-10-17","Statement": [{"Si…...
C#中常见的锁以及用法--18
目录 一.C#中存在的锁 二.锁的作用 三.锁的概念和定义 关于锁的完整代码示例 代码逐层剖析: 全局变量与同步变量 Lock(锁)关键字示例 Monitor(监视器锁)示例 Mutex(互斥量)示例(支持跨进程同步) SemaphoreSlim(信号量)示例 ReadWriterLockSlim(读写锁)示例 SpinLock…...
【数据分享】1929-2024年全球站点的逐年平均气温数据(Shp\Excel\无需转发)
气象数据是在各项研究中都经常使用的数据,气象指标包括气温、风速、降水、湿度等指标,其中又以气温指标最为常用!说到气温数据,最详细的气温数据是具体到气象监测站点的气温数据!本次我们为大家带来的就是具体到气象监…...
Docker部署MySQL 5.7:持久化数据的实战技巧
在生产环境中使用Docker启动MySQL 5.7时,需要考虑数据持久化、配置文件管理、安全性等多个方面。以下是一个详细的步骤指南。 1. 准备工作 (1)创建挂载目录 在宿主机上创建用于挂载的目录,以便持久化数据和配置文件。 sudo mkdi…...
二叉树和堆
树概念及结构(了解) 树的概念(看看就行) 树是一种 非线性 的数据结构,它是由 n ( n>0 )个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树,也就是…...
Zookeeper(15)Zookeeper的ZooKeeper API包含哪些主要操作?
Zookeeper 的 ZooKeeper API 提供了一系列操作来管理 Zookeeper 的数据节点(znodes)。这些操作主要包括创建节点、删除节点、读取节点数据、设置节点数据、列出子节点、检查节点是否存在,以及注册 Watcher 等。以下是这些操作的详细介绍和代码…...
深入浅出:Go语言os包中的API使用指南
深入浅出:Go语言os包中的API使用指南 引言 Go语言以其简洁、高效和强大的生态系统著称,是现代编程中不可或缺的一部分。其中,os包作为Go标准库的一部分,提供了丰富的API来与操作系统进行交互。本文将深入探讨os包中的核心功能,并通过实际案例帮助读者更好地理解和应用这些…...
【云岚到家】-day02-客户管理-认证授权
第二章 客户管理 1.认证模块 1.1 需求分析 1.基础概念 一般情况有用户交互的项目都有认证授权功能,首先我们要搞清楚两个概念:认证和授权 认证: 就是校验用户的身份是否合法,常见的认证方式有账号密码登录、手机验证码登录等 授权:则是该用…...
vben5 admin ant design vue如何使用时间范围组件RangePicker
本文参考:https://pusdn-dev.feishu.cn/wiki/VF4hwBAUliTE6TkUPKrcBNcZn9f?fromfrom_copylink 由PUSDN整理发行,收录时请保留PUSDN。 前端组件专题 年月日时间范围表单回显RangePicker 推荐使用多个字段存储,不推荐用英文逗号拼接时间&am…...
安全策略配置实验
安全策略配置实验 1.拓扑 2.需求 2、办公区PC在工作日时间(周一至周五,早8到晚6)可以正常访问OA srver,其他时间不允许 3、办公区PC可以在任意时刻访问web server 4、生产区PC可以在任意时刻访问OA Server,但是不能访问Web server 5、特…...
Win10安装WebODM和操作全流程
效果 以下是在 Windows 10 上安装和部署 WebODM 的详细教程: 一、安装 Docker Desktop for Windows 1、访问 Docker 官方网站:https://www.docker.com/products/docker-desktop 。 2、下载 Docker Desktop for Windows 的安装程序。 3、运行安装程序: 双击下载的安装程序,…...
wireshark抓路由器上的包 抓包路由器数据
文字目录 抓包流程概述设置抓包配置选项 设置信道设置无线数据包加密信息设置MAC地址过滤器 抓取联网过程 抓包流程概述 使用Omnipeek软件分析网络数据包的流程大概可以分为以下几个步骤: 扫描路由器信息,确定抓包信道;设置连接路由器的…...
第8章:Python TDD处理货币类代码重复问题
写在前面 这本书是我们老板推荐过的,我在《价值心法》的推荐书单里也看到了它。用了一段时间 Cursor 软件后,我突然思考,对于测试开发工程师来说,什么才更有价值呢?如何让 AI 工具更好地辅助自己写代码,或许…...
C#,入门教程(01)—— Visual Studio 2022 免费安装的详细图文与动画教程
通过本课程的学习,你可以掌握C#编程的重点,享受编程的乐趣。 在本课程之前,你无需具备任何C#的基础知识,只要能操作电脑即可。 不过,希望你的数学不是体育老师教的。好的程序是数理化的实现与模拟。没有较好的数学基础…...
Agent Laboratory: Using LLM Agents as Research Assistants 论文简介
加速机器学习研究的智能实验室——Agent Laboratory 1. 引言 随着人工智能技术的飞速发展,机器学习领域正以前所未有的速度推进科学发现和技术创新。然而,传统的科学研究模式往往受到时间、资源和专业知识限制,阻碍了研究者们探索新想法的能…...
cuda + cudnn安装
1.安装CUDA Toolkit 在设备管理器(此电脑–右键–属性)的显示适配器中可以查看自己的显卡型号,去下载对应的CUDA Toolkit 。或者输入以下命令查看Driver Version ,cuda Version:12.2代表12.2版本以下兼容可以进行安装 …...
Next.js 实战 (八):使用 Lodash 打包构建产生的“坑”?
前言 最近一直在折腾 Nextjs15 ,也在断断续续地写《Next.js15 实战系列》的文章,后来总感觉文章如果没有线上效果预览差点意思,所以就想着先把目前做的项目先部署上线,后续再慢慢添加新功能。 因为之前没有部署过 Nextjs15 工程…...
owasp SQL 注入-03 (原理)
1: 先看一下注入界面: 点submit 后,可以看到有语法报错,说明已经起作用了: 报如下的错误: You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near at line 1 2:…...
wireshark工具简介
目录 1 wireshark介绍 2 wireshark抓包流程 2.1 选择网卡 2.2 停止抓包 2.3 保存数据 3 wireshark过滤器设置 3.1 显示过滤器的设置 3.2 抓包过滤器 4 wireshark的封包列表与封包详情 4.1 封包列表 4.2 封包详情 参考文献 1 wireshark介绍 wireshark是非常流行的网络…...
队列的基本用法
以下是关于 C 语言中队列的详细知识,包括队列的生成、相关函数使用以及其他重要概念: 一、队列的概念 队列是一种线性数据结构,它遵循先进先出(First In First Out,FIFO)的原则,就像日常生活中…...
OpenHarmony-7.IDL工具
IDL 工具 1.openharmony IDL工具 在OpenHarmony中,当应用/系统服务的客户端和服务端进行IPC(Inter-Process Communication)跨线程通信时,需要定义双方都认可的接口,以保障双方可以成功通信,OpenHarmony ID…...
封装Redis工具类
基于StringRedisTemplate封装一个缓存工具类,满足以下需求: 方法1:将任意Java对象序列化为json并存储在string类型的key中,并且可以设置TTL过期时间 方法2:将任意Java对象序列化为json并存储在string类型的key中,并且可以设置TTL过期时间,用于处理缓存击穿问题 方法3:根据指定的…...
将n变为一个可以被表示为2^{a}+2^{b}的正整数m
给出一个正整数n,需要将n变为一个可以被表示为的正整数m,其中a和b都是非负整数且a!b,你可以进行两种操作: 1.令n加1 2.令n减1 请你求出最少需要多少次操作才能将n变成满足条件的m。 输入格式 输入一个整数,代表n。…...
第2章:Python TDD构建Dollar类基础
写在前面 这本书是我们老板推荐过的,我在《价值心法》的推荐书单里也看到了它。用了一段时间 Cursor 软件后,我突然思考,对于测试开发工程师来说,什么才更有价值呢?如何让 AI 工具更好地辅助自己写代码,或许…...
搭建一个基于Spring Boot的校园台球厅人员与设备管理系统
搭建一个基于Spring Boot的校园台球厅人员与设备管理系统可以涵盖多个功能模块,例如用户管理、设备管理、预约管理、计费管理等。以下是一个简化的步骤指南,帮助你快速搭建一个基础的系统。 — 1. 项目初始化 使用 Spring Initializr 生成一个Spring …...
JavaScript系列(33)--微前端架构详解
JavaScript微前端架构详解 🏗️ 今天,让我们深入了解JavaScript的微前端架构,这是一种用于构建和管理大型前端应用的现代架构模式。 微前端基础概念 🌟 💡 小知识:微前端是一种将前端应用分解成更小、更易…...
第6章:Python TDD实例变量私有化探索
写在前面 这本书是我们老板推荐过的,我在《价值心法》的推荐书单里也看到了它。用了一段时间 Cursor 软件后,我突然思考,对于测试开发工程师来说,什么才更有价值呢?如何让 AI 工具更好地辅助自己写代码,或许…...
Ubuntu 24.04 LTS 服务器折腾集
目录 Ubuntu 更改软件源Ubuntu 系统语言英文改中文windows 远程链接 Ubuntu 图形界面Windows 通过 openssh 连接 UbuntuUbuntu linux 文件权限Ubuntu 空闲硬盘挂载到 文件管理器的 other locationsUbuntu 开启 SMB 服务,并通过 windows 访问Ubuntu安装Tailscale&am…...
物联网在烟草行业的应用
物联网技术在烟草行业的应用 物联网技术在烟草行业的应用主要体现在以下几个方面: 智能制造 :物联网技术可以实现对生产过程中的关键参数进行实时监测,确保产品的质量稳定可靠。同时,通过对设备的远程维护和故障诊断,…...
2024年度总结:从后端Java到全栈成长的蜕变
目录 前言1. 用数据与实践书写成长篇章2. 技术与生活的双重蜕变3. 技术的进阶与生活的绽放 前言 今年是我入行的第十年,也是记录在CSDN平台上的第五年。这五年来,我始终坚持记录成长的点滴,将个人事业与博客创作紧密相连。一路走来࿰…...
详解构造函数和析构函数
⼀个类,我们不写的情况下编译器会默认⽣成以下6个默认成员函数。 下面我们详细介绍的是构造函数和析构函数,它们的主要作用分别是初始化工作和清理工作。 构造函数 1、构造函数的概念 构造函数虽名里带着“构造”但是其实际上并不是说开辟空间创建对…...
npm操作大全:从入门到精通
引言 在现代前端开发中,npm(Node Package Manager)是不可或缺的工具。无论是安装依赖、管理项目,还是发布自己的包,npm都扮演着重要的角色。本文将带你从npm的基础操作开始,逐步深入到高级用法,…...
ChatGPT 写作系列
ChatGPT 辅助写作 | 专栏 1 写作核心 先讲一下 ChatGPT 写作的核心。核心就是需要有文章大纲,而且文章大纲要足够细致。 具体怎么做呢? 提前准备多级标题大纲,刚开始有两个级别的标题就行,等用熟练了再细化。分一级标题&…...
kubernetes 集群搭建(kubeadm方式)
随着容器技术的日益普及,Kubernetes 作为最受欢迎的容器编排平台之一,已经成为现代云原生应用部署不可或缺的一部分。对于想要快速构建和管理 Kubernetes 集群的人来说,kubeadm 提供了一种简单而强大的工具。本文将详细介绍如何使用 kubeadm …...
OpenWrt 中使用 LuCI 界面部署 Docker 镜像
本篇博客将介绍如何在 OpenWrt 上使用 LuCI 部署 Docker 镜像,以 "hello-world" 镜像为例。 前提条件 已安装支持 Docker 的 OpenWrt 系统。 Docker 服务已在 OpenWrt 上成功安装并运行。 LuCI Docker 插件(luci-app-docker 或类似的管理界…...
阿里云 Serverless 助力盟主直播:高并发下的稳定性和成本优化
在直播场景中,阿里云 Serverless 应用引擎 SAE 提供的无缝弹性伸缩与极速部署能力,确保直播间高并发时的流畅体验,降低了我们的运营成本,简化了运维流程。结合阿里云云原生数据库 PolarDB 的 Serverless 能力,实现了数…...
C++ 多态 初学笔记
多态 虚函数虚函数的使用条件 虚函数详解对象多态多重继承时,类型转换的练习(1)情况1:(2)情况2:(3)情况3:(4)情况4: 对象多…...
深入剖析 Java 的 synchronized 锁升级过程
前言 在 Java 并发编程领域,synchronized关键字堪称保障线程安全的中流砥柱。随着 JDK 版本的迭代演进,synchronized锁的性能优化也在持续推进,其中锁升级机制尤为关键。本文将深度剖析synchronized锁从偏向锁、轻量级锁到重量级锁的升级历程…...
当文件补丁修改器因为文件操作权限有问题时,可以将文件拷贝到普通目录操作
文章目录 当文件补丁修改器因为文件操作权限有问题时,可以将文件拷贝到普通目录操作概述笔记直接在安装目录打补丁失败的情况将目标程序拷贝到补丁修改器的解压目录打补丁成功的情况备注END 当文件补丁修改器因为文件操作权限有问题时,可以将文件拷贝到普…...
【TCP】rfc文档
tcp协议相关rfc有哪些 TCP(传输控制协议)是一个复杂的协议,其设计和实现涉及多个RFC文档。以下是一些与TCP协议密切相关的RFC文档列表,按照时间顺序排列,涵盖了从基础定义到高级特性和优化的各个方面: 基…...
Linux探秘坊-------3.开发工具详解(1)
1 初识vim编辑器 创建第一个vim编辑的代码 1.新建文件 2.使用vim打开 3.打开默认是命令模式,写代码需要在屏幕上输出“i”字符 1.写完代码后要按Esc键退出到指令模式2.再按shift:wq即可保存并退出vim (因为不支持鼠标,通常 使用键盘上的箭…...
如何在Python中进行JSON数据的序列化和反序列化?
在Python中,JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,易于人阅读和编写,同时也易于机器解析和生成。Python内置的json模块提供了简单易用的方法来实现数据的序列化和反序列化。下面将详细介绍如何…...
SpringMVC (1)
目录 1. 什么是Spring Web MVC 1.1 MVC的定义 1.2 什么是Spring MVC 1.3 Spring Boot 1.3.1 创建一个Spring Boot项目 1.3.2 Spring Boot和Spring MVC之间的关系 2. 学习Spring MVC 2.1 SpringBoot 启动类 2.2 建立连接 1. 什么是Spring Web MVC 1.1 MVC的定义 MVC 是…...
Redis 3.2.1在Win10系统上的安装教程
诸神缄默不语-个人CSDN博文目录 这个文件可以跟我要,也可以从官网下载:https://github.com/MicrosoftArchive/redis/releases 这个是微软以前维护的Windows版Redis安装包,如果想要比较新的版本可以从别人维护的项目里下(https://…...
springboot医院信管系统
摘 要 随着信息技术和网络技术的飞速发展,人类已进入全新信息化时代,传统管理技术已无法高效,便捷地管理信息。为了迎合时代需求,优化管理效率,各种各样的管理系统应运而生,各行各业相继进入信息管理时代&a…...
A6.Springboot-LLama3.2服务自动化构建(三)——编写Pipeline构建仓库初始化脚本
下面我们接着上一篇文章《A5.Springboot-LLama3.2服务自动化构建(二)——Jenkins流水线构建配置初始化设置》继续往下分析,编写Pipeline构建脚本。 一、统一Shell执行环境 Jenkins执行Shell脚本时,会在Jenkins节点上创建一个临时的环境来执行该脚本。这个环境包含了Jenki…...
Android 10.0 自定义Window窗口层级新增Type类型功能实现
1.前言 在10.0的系统rom定制化开发过程中,在产品开发过程中,需要新增Window窗口类型来显示 特殊的窗口层级,Window窗口就是根据Type类型来显示的,所以接下来需要新增Type类型来 新增Window窗口显示类型,如图 2.自定义Window窗口层级新增Type类型功能实现的核心类 framew…...
Linux中的基本指令(一)
一、Linux中指令的存在意义 Linux中,通过输入指令来让操作系统执行,以此达到控制操作系统的目的,类似于Windows中的双击,右键新建文件,新建文件夹等 1.补:关于屏幕的几个操作指令 ①清屏指令 clear 回…...