首页 > 其他分享 >70.爬楼梯

70.爬楼梯

时间:2022-11-03 23:25:06浏览次数:52  
标签:楼顶 爬楼梯 示例 复杂度 number let 70

假设你正在爬楼梯。需要 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 阶 

提示:

  • 1 <= n <= 45

方法一:动态规划

时间复杂度:O(n)

空间复杂度:O(1)

 1 /**
 2  * @param {number} number
 3  * @return {number}
 4  */
 5 var climbStairs = function(n) {
 6     let p = 0,
 7         q = 0,
 8         r = 1;
 9     for (let i = 1; i <= n; ++i) {
10         p = q;
11         q = r;
12         r = p + q;
13     }
14     return r;
15 };

 

标签:楼顶,爬楼梯,示例,复杂度,number,let,70
From: https://www.cnblogs.com/icyyyy/p/16856226.html

相关文章

  • TM7707提高转换速率的非常规方法
    TM7707在滤波器设置为4000时转换速率只有5HZ,两通道的情况下,单通道就只有2.5Hz的数据转换速率了。有没有什么方法,能让转换精度不变,转换速率提高?答案是有的! 不过这是一......
  • [题解] HDU7060 Separated Number 思路整理
    题目链接HDU7060SeparatedNumber题目大意给一个\(n\)位数,把该数字分成\(k\)段,每种方案的贡献为其分割出的段的数字之和。求所有分法的贡献之和(对\(998244353\)......
  • 代码随想录day38 | 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
    509.斐波那契数题目|文章思路确实数组及其含义确定递推公式数组的初始化条件确定遍历顺序举例推导dp数组实现点击查看代码classSolution{public:in......
  • Codeforces 1670 E. Hemose on the Tree
    题意给你个数p,n=2^p;有一棵树有n个节点,告诉你怎么连边;每个点有个权值,每条边也有个权值,权值需要自行分配,[1,2,3..n...2n-1],总共2n-1个权值;你需要选一个节点,使得他到所......
  • 【XSY3470】Cherry(后缀数组)
    题意:给一个长度为\(n\)的串\(S\)和一个长度为\(b\)的串\(B\),有\(m\)个文本串,初始它们都是空串。需要支持\(q\)个操作,每个操作要么是给某个文本串后面接上串\(B......
  • 【XSY3270】Domino Colorings(轮廓线dp,状压)
    若已经知道了每个格子的颜色,我们可以用轮廓线DP(类似插头DP)判断棋盘是否能被多米诺骨牌填满,设\(dp[S]\)表示是否存在某种填法使得轮廓线每个位置是否被填的状态为\(S\)......
  • 最小花费爬楼梯 -- 动态规划
    方法一递归 importjava.util.*;publicclassSolution{/***代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可**......
  • 代码随想录算法训练营第三天 | 203.移除链表元素 、707.设计链表、 206.反转链表
    链表这个数据结构我很少用到,本科的时候学过忘的都差不多了,感谢知道了可以直接添加一个虚拟头的操作!203.移除链表元素  707.设计链表: 206.反转链表未完成 ......
  • 动态规划-746. 使用最小花费爬楼梯
    题目描述给你一个整数数组cost,其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下......
  • 动态规划 -70. 爬楼梯
    题目描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢?思路碰到这类题我们可以通过高中学的数学归纳......