leetcode中如何解决爬楼梯问题
发表于:2024-10-23 作者:千家信息网编辑
千家信息网最后更新 2024年10月23日,小编给大家分享一下leetcode中如何解决爬楼梯问题,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!题目链接https:/
千家信息网最后更新 2024年10月23日leetcode中如何解决爬楼梯问题
小编给大家分享一下leetcode中如何解决爬楼梯问题,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
题目链接
https://leetcode-cn.com/problems/climbing-stairs/
题目描述
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n
是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解题方案
第一种思路
标签:数学
如果观察数学规律,可知本题是斐波那契数列,那么用斐波那契数列的公式即可解决问题,公式如下:
时间复杂度:O(logn)
第一种思路代码
Java版本
class Solution {
public int climbStairs(int n) {
double sqrt_5 = Math.sqrt(5);
double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
return (int)(fib_n / sqrt_5);
}
}
JavaScript版本
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
const sqrt_5 = Math.sqrt(5);
const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
return Math.round(fib_n / sqrt_5);
};
第二种思路
标签:动态规划
本问题其实常规解法可以分成多个子问题,爬第n阶楼梯的方法数量,等于2部分之和
爬上n-1阶楼梯的方法数量。因为再爬1阶就能到第n阶
爬上n-2阶楼梯的方法数量,因为再爬2阶就能到第n阶
所以我们得到公式dp[n] = dp[n-1] + dp[n-2]
同时需要初始化
dp[0]=1
和dp[1]=1
时间复杂度:O(n)
第二种思路代码
Java版本
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
JavaScript版本
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
const dp = [];
dp[0] = 1;
dp[1] = 1;
for(let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
画解
以上是"leetcode中如何解决爬楼梯问题"这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注行业资讯频道!
楼梯
方法
问题
思路
楼顶
版本
公式
数量
篇文章
复杂
代码
内容
复杂度
数列
数学
时间
标签
示例
题目
解释
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
湖北服务器电源厂家
网络技术网线制作实验报告
维基数据库多大
电力系统网络安全公司
公安县网络安全宣传周活动
软件开发英语不会能学吗
米内网数据库 试用账号
襄阳博沅互联网科技有限公司
数据库连接怎么用java连起来
博兴企业管理软件开发定制
olap用什么数据库
谈谈我国网络安全
游戏服务器租用价目表
郑州众易软件开发
海南大数据卫星授时服务器
收费站网络安全事故
瑞丢死服务器
打开数据库总是慢怎么办
李沧区手机软件开发哪家靠谱
广州省情数据库
linux获取服务器时间命令
天枢数据库插入异常怎么处理
专门运行python的服务器
如何关闭网络安全设置
x299对应的服务器板子
svn服务器端配置
打开数据库总是慢怎么办
重庆南川蔬菜软件开发
材料力学课件软件开发
八cpu服务器主板