剑指Offer：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

暴力法

---

思路：

按照函数调用的递归树,记录符合条件的跳跃操作：

python代码：

class Solution:
    def __init__(self):
        self.solutions = 0
        pass

    def jump(self, start, end):
        if start > end:
            return 0
        elif start == end:
            return 1
        return self.jump(start + 1, end) + self.jump(start + 2, end)

    def jumpFloor(self, number):
        if number == 0:
            return 0
        self.solutions = self.jump(0, number)
        return self.solutions


if __name__ == '__main__':
    s = Solution()
    for i in range(0, 20):
        s.solutions = 0
        print(s.jumpFloor(i), end=',')

时间复杂度： - 递归访问所有的节点

空间负责度：- 递归树可达的深度

 

记忆化递归

---

在暴力法递归中，存在很多重复的计算，因此可以对于特定台阶数记录其存在的方案数，以后直接访问记录即可。

 python代码：

class Solution:
    def __init__(self):
        self.solutions = 0
        self.mem = []
        pass

    def jump(self, start, end):
        if start > end:
            return 0
        elif start == end:
            return 1
        if self.mem[start] > 0:
            return self.mem[start]
        self.mem[start] = self.jump(start + 1, end) + self.jump(start + 2, end)
        return self.mem[start]

    def jumpFloor(self, number):
        self.mem = [0 for _ in range(number)]

        if number == 0:
            return 0
        self.solutions = self.jump(0, number)
        return self.solutions


if __name__ == '__main__':
    s = Solution()
    for i in range(0, 20):
        s.solutions = 0
        print(s.jumpFloor(i), end=',')

时间复杂度：

空间负责度：

 

动态规划

---

由上述的方法，抛开时间复杂度和空间复杂度，我们已经可以找到一系列输出的序列。

根据一个神奇的网站：OEIS，我们可以找到序列之间存在的关系：斐波那契数列

python代码：

class Solution:
    def jumpFloor(self, number):
        res = [0, 1, 2]
        while len(res) <= number:
            res.append(res[-1]+res[-2])
        return res[number]


if __name__ == '__main__':
    s = Solution()
    for i in range(0, 20):
        print(s.jumpFloor(i), end=',')

由于用res存储了对0～number不同长度的方案数目，所以

时间复杂度：

空间复杂度：，如果只记录长度为number时的方案数，空间复杂度可降低为