假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。 - 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
- show the code:
### code1
class Solution:
def climbStairs(self,n):
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n-1)+self.climbStairs(n-2)
### code2
class Solution:
def climbStairs(self, n: int) -> int:
a,b = 1,2
if n == 1:
return a
if n == 2:
return b
for i in range(n-2):
a,b = b,a+b
return b
- 此题是经典题,一看到题就应该联想到斐波拉契数列。代码一是最直接的解法,但是会重复地求很多次中间值,所以时间复杂度在
2^n
指数级别,所以肯定是不理想的,甚至都不能AC。 - 代码二则省去了计算重复值,而且不用储存中间值,只需要储存前两个值即可,因此在时间和空间上都有较大提升。
- 有关此类题目的解法在力扣官方题解上有很多方法,其中像矩阵法和公式法都只需要
logn
的复杂度。链接如下:爬楼梯方法
网友评论