青蛙跳台阶

青蛙爬上最后一级台阶的时候，可能是一次跳了一步，也可能是一次跳了两步
所以方案数f(n) = f(n-1) + f(n-2)

递归的方法

超时无法通过OJ，

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

动态规划的方法

时间复杂度和空间复杂度都是O(n)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        result = [1] * (n+1)
        result[2] = 1
        for i in range(2, n+1):
            result[i] = result[i-1] + result[i-2]
        return result[n]

考虑到其实每次只需要结果值的前两个值，所以我们可以用p,q,r轮动的方式去推进
可以降低空间复杂度到O(1)

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

还有矩阵快速幂的方法

如果一个问题可与转化为求解一个矩阵的 n次方的形式，那么可以用快速幂来加速计算

还可以求通项公式