假设你正在爬楼梯。需要 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的复杂度。链接如下：爬楼梯方法
