70. 爬楼梯(easy)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：
   输入： 3
   输出： 3
   解释： 有三种方法可以爬到楼顶。
3. 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 2 阶
5. 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的复杂度。链接如下：爬楼梯方法