[数据结构与算法]LeetCode简单题之爬楼梯

题目

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

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：
   输入：n = 3
   输出：3
   解释：有三种方法可以爬到楼顶。
3. 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 2 阶
5. 2 阶 + 1 阶
   提示：
   1 <= n <= 45
   来源：力扣（LeetCode）

解题思路

??假设当前你已经到达第n层，那么你可能是由第n-1层跳过来也可能是从第n-2层跳过来，但是不管从哪层跳过来都需要计入总数，因为题目记录的是有几种方法。故有f(n)=f(n-1)+f(n-2)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n==1:
            return 1
        if n==2:
            return 2
        return self.climbStairs(n-1)+self.climbStairs(n-2)

??实际上跳上当前台阶的方法种数只和前面两种情况相关，所以不需要像上面一样将很多的数据压入栈中，只需要保存最近的两次情况结果即可。

class Solution:
    def climbStairs(self, n: int) -> int:
        p,q,r=0,0,1
        for i in range(n):
            p,q=q,r
            r=p+q
        return r