爬楼梯
爬楼梯
夜雨柠檬难度
简单
中等
困难
题目
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
提示:
- 1 <= n <= 45
题解
我的思路:
先找规律,f(1) = 1,f(2) = 2,f(3) = 3,f(4) = 5,f(5) = 8;
由此可以推出:f(x) = f(x - 1) + f(x - 2) x > 0。
因为一次只能上1个台阶或者2个台阶,如果爬 n 个台阶,那么情况就两种;一种是最后一步走一个台阶 f(n - 1),另一种是最后一步走两个台阶 f(n - 2),一共就是 f(n) = f(n - 1) + f(n - 2)。
1 | class Solution { |
这里的 q 是 f(n - 1),p 是 f(n - 2),r 是 f(n)。
复杂度分析:
时间复杂度:循环执行 n
次,每次花费常数的时间代价,故渐进时间复杂度为 O(n)
。
空间复杂度:这里只用了常数个变量作为辅助空间,故渐进空间复杂度为 O(1)
。
评论
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果