70. 爬楼梯【 力扣(LeetCode) 】
一、题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 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 阶
二、解题思路
- 基本思路:记爬 2 个台阶的个数为 k ,该题目可以转化为计算 k = 0,1,2,…,的方案数,例如:k = 0,表示每次只爬一个台阶,方案数为 C n − k k = C n 0 = 1 C_{n-k}^k=C_n^0=1 Cn−kk=Cn0=1 ;k = 1 ,表示有一次是爬两个台阶,其他都是爬一个台阶,方案数就是 C n − k k = C n − 1 1 = n − 1 C_{n-k}^k=C_{n-1}^1=n-1 Cn−kk=Cn−11=n−1 ,依次类推,总方案数就是 ∑ k = 0 n 2 C n − k k \sum_{k=0}^{\frac n2}C_{n-k}^k k=0∑2nCn−kk
- 具体思路:
- 暴力解:写一个函数计算 C n k = n ( n − 1 ) ⋯ ( n − k + 1 ) k ! C_n^k=\frac{n(n-1)\cdots(n-k+1)}{k!} Cnk=k!n(n−1)⋯(n−k+1)
- 动态规划:计算 C n k C_n^k Cnk 表,其中 C n k = C n − 1 k − 1 + c n − 1 k C_n^k=C_{n-1}^{k-1}+c_{n-1}^k Cnk=Cn−1k−1+cn−1k
三、参考代码
3.1 暴力解
时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( 1 ) O(1) O(1)
数据可能会溢出
// 计算cnk,k 表示爬 2 个楼梯的个数,n 表示楼梯总数 - k
int c(int k,int n){long long int a=1,b=1;for(int i=0;i<k;i++){a*=n-i;b*=k-i;}return a/b;
}int climbStairs(int n) {int sum=0;for(int i=0;2*i<=n;i++){sum+=c(i,n-i);}return sum;
}
3.2 动态规划
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
const static int max=45;
long c[max+1][max+1];
// dp方法,核心是 c[n][k]=c[n-1][k-1]+c[n-1][k]
void compute_c(){for(int i=0;i<=max;i++){ c[i][0]=c[i][i]=1;}for(int n=1;n<=max;n++){for(int k=1;k<n;k++){c[n][k]=c[n-1][k-1]+c[n-1][k];}}
}
int climbStairs(int n) {int sum=0;compute_c();for(int i=0;2*i<=n;i++){sum+=c[n-i][i];}return sum;
}
相关文章:
70. 爬楼梯【 力扣(LeetCode) 】
一、题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 二、测试用例 示例 1: 输入:n 2 输出:2 解释:有两种方法可以爬到楼顶。 1. 1 阶…...
R语言优雅的把数据基线表(表一)导出到word
基线表(Baseline Table)是医学研究中常用的一种数据表格,用于在研究开始时呈现参与者的初始特征和状态。这些特征通常包括人口统计学数据、健康状况和疾病史、临床指标、实验室检测、生活方式、社会经济等。 本人在既往文章《scitb包1.6版本发…...
XMl基本操作
引言 使⽤Mybatis的注解⽅式,主要是来完成⼀些简单的增删改查功能. 如果需要实现复杂的SQL功能,建议使⽤XML来配置映射语句,也就是将SQL语句写在XML配置⽂件中. 之前,我们学习了,用注解的方式来实现MyBatis 接下来我们…...
Linux——Shell脚本和Nginx反向代理服务器
1. Linux中的shell脚本【了解】 1.1 什么是shell Shell是一个用C语言编写的程序,它是用户使用Linux的桥梁 Shell 既是一种命令语言,有是一种程序设计语言 Shell是指一种应用程序,这个应用程序提供了一个界面,用户通过这个界面访问…...
pyspark使用 graphframes创建和查询图的方法
1、安装graphframes的步骤 1.1 查看 spark 和 scala版本 在终端输入: spark-shell --version 查看spark 和scala版本 1.2 在maven库中下载对应版本的graphframes https://mvnrepository.com/artifact/graphframes/graphframes 我这里需要的是spark 2.4 scala 2.…...
【web】-flask-简单的计算题(不简单)
打开页面是这样的 初步思路,打开F12,查看头,都发现了这个表达式的base64加密字符串。编写脚本提交答案,发现不对; 无奈点开source发现源代码,是flask,初始化表达式,获取提交的表达式࿰…...
Apache Sqoop
Apache Sqoop是一个开源工具,用于在Apache Hadoop和关系型数据库(如MySQL、Oracle、PostgreSQL等)之间进行数据的批量传输。其主要功能包括: 1. 数据导入:从关系型数据库(如MySQL、Oracle等)中将…...
【Python】TensorFlow介绍与实战
TensorFlow介绍与使用 1. 前言 在人工智能领域的快速发展中,深度学习框架的选择至关重要。TensorFlow 以其灵活性和强大的社区支持,成为了许多研究者和开发者的首选。本文将进一步扩展对 TensorFlow 的介绍,包括其优势、应用场景以及在最新…...
第100+16步 ChatGPT学习:R实现Xgboost分类
基于R 4.2.2版本演示 一、写在前面 有不少大佬问做机器学习分类能不能用R语言,不想学Python咯。 答曰:可!用GPT或者Kimi转一下就得了呗。 加上最近也没啥内容写了,就帮各位搬运一下吧。 二、R代码实现Xgboost分类 (…...
【操作系统】定时器(Timer)的实现
这里写目录标题 定时器一、定时器是什么二、标准库中的定时器三、实现定时器 定时器 一、定时器是什么 定时器也是软件开发中的⼀个重要组件.类似于⼀个"闹钟".达到⼀个设定的时间之后,就执行某个指定 好的代码. 定时器是⼀种实际开发中⾮常常用的组件. ⽐如⽹络通…...
鸿蒙Navigation路由能力汇总
基本使用步骤: 1、新增配置文件router_map: 2、在moudle.json5中添加刚才新增的router_map配置: 3、使用方法: 属性汇总: https://developer.huawei.com/consumer/cn/doc/harmonyos-references/ts-basic-compone…...
1:1公有云能力整体输出,腾讯云“七剑”下云端
【全球云观察 | 科技热点关注】 曾几何时,云计算技术的兴起,为千行万业的数字化创新带来了诸多新机遇,同时也催生了新产业新业态新模式,激发出高质量发展的科技新动能。很显然,如今的云创新已成为高质量发…...
【iOS】APP仿写——网易云音乐
网易云音乐 启动页发现定时器控制轮播图UIButtonConfiguration 发现换头像 我的总结 启动页 这里我的启动页是使用Xcode自带的启动功能,将图片放置在LaunchScreen中即可。这里也可以通过定时器控制,来实现启动的效果 效果图: 这里放一篇大…...
react 快速入门思维导图
在掌握了react中一下的几个步骤和语法,基本上就可以熟练的使用react了。 1、组件的使用。react创建组件主要是类组件和函数式组件,类组件有生命周期,而函数式组件没有。 2、jsx语法。react主要使用jsx语法,需要使用babel和webpa…...
微软研究人员为电子表格应用开发了专用人工智能LLM
微软的 Copilot 生成式人工智能助手现已成为该公司许多软件应用程序的一部分。其中包括 Excel 电子表格应用程序,用户可以在其中输入文本提示来帮助处理某些选项。微软的一组研究人员一直在研究一种新的人工智能大型语言模型,这种模型是专门为 Excel、Go…...
[算法题]两个链表的第一个公共结点
题目链接: 两个链表的第一个公共结点 图示: 两个链表如果长度一致, 那么两人同时一人走一步, 如果存在公共结点, 迟早会相遇, 但是如果长度不一致单存在公共结点, 两人同时一人走一步不会相遇, 此时定义两个变量, node1 和 node2, 这两个变量分别从 x1 和 x2 开始走, 当其走完…...
MySQL事务管理(上)
目录 前言 CURD不加控制,会有什么问题? CURD满足什么属性,能解决上述问题? 事务 什么是事务? 为什么会出现事务 事务的版本支持 事务提交方式 查看事务提交方式 改变 MySQL 的自动提交模式: 事务常见操作方式 前…...
HTML2048小游戏
源代码在效果图后面 效果图 源代码 <!DOCTYPE html> <html lang"zh-CN"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>2048 Game&l…...
为 android编译 luajit库、 交叉编译
时间:20200719 本机环境:iMac2017 macOS11.4 参考: 官方的文档:Use the NDK with other build systems 写在前边:交叉编译跟普通编译类似,无非是利用特殊的编译器、链接器生成动态或静态库; make 本质上是按照 Make…...
【音视频】音频重采样
文章目录 前言音频重采样的基本概念音频重采样的原因1. 设备兼容性2. 文件大小和带宽3. 音质优化4. 标准化和规范5. 多媒体同步6. 降低处理负载重采样的注意事项 总结 前言 音频重采样是指将音频文件的采样率转换成另一种采样率的过程。这在音频处理和传输中是一个常见且重要的…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
前端开发者常用网站
Can I use网站:一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use:Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站:MDN JavaScript权威网站:JavaScript | MDN...
PydanticAI快速入门示例
参考链接:https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...
41道Django高频题整理(附答案背诵版)
解释一下 Django 和 Tornado 的关系? Django和Tornado都是Python的web框架,但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架,鼓励快速开发和干净、实用的设计。它遵循MVC设计,并强调代码复用。Django有…...
如何做好一份技术文档?从规划到实践的完整指南
如何做好一份技术文档?从规划到实践的完整指南 🌟 嗨,我是IRpickstars! 🌌 总有一行代码,能点亮万千星辰。 🔍 在技术的宇宙中,我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...
职坐标物联网全栈开发全流程解析
物联网全栈开发涵盖从物理设备到上层应用的完整技术链路,其核心流程可归纳为四大模块:感知层数据采集、网络层协议交互、平台层资源管理及应用层功能实现。每个模块的技术选型与实现方式直接影响系统性能与扩展性,例如传感器选型需平衡精度与…...
