方法一：递归 题目分析，假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n-1个台阶，一种是走到第n-2个台阶。所以f[n] = f[n-1] + f[n-2]. 那么初始条件了，f[0] = f[1] = 1。 所以就变成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1，目标求f[n] 看到公式很亲切，代码秒秒钟写完。 
class Solution:
    def jumpFloor(self, number):
        # write code here
         if number <=1:
            return 1
         return self.jumpFloor(number-1) +self.jumpFloor(number-2)
时间复杂O(2^n) 空间复杂度：递归栈的空间
方法二：记忆化搜索 拿求f[5] 举例

通过图会发现，方法一中，存在很多重复计算，因为为了改进，就把计算过的保存下来。 那么用什么保存呢？一般会想到map， 但是此处不用牛刀，此处用数组就好了。 


class Solution:
    def jumpFloor(self, number):
        # write code here
        f = [0]*100
        if number <=1:return 1
        if f[number] >0: return f[number]
        f[number] = self.jumpFloor(number-1)+self.jumpFloor(number-2)
        return f[number]

方法三：动态规划

虽然方法二可以解决此题了，但是如果想让空间继续优化，那就用动态规划，优化掉递归栈空间。 方法二是从上往下递归的然后再从下往上回溯的，最后回溯的时候来合并子树从而求得答案。 那么动态规划不同的是，不用递归的过程，直接从子树求得答案。过程是从下往上。

我们可以通过推理来找出。
第3位可以由第1阶台阶跳2阶或第2阶段跳1阶段得出。
第4位可以由第2阶台阶跳2阶或第3阶段跳1阶段得出。
第5位可以由第3阶台阶跳2阶或第4阶段跳1阶段得出。
......
最后可以得出：
dp[i]=dp[i-1]+dp[i-2];dp[i]=dp[i−1]+dp[i−2];
其中dp[i]表示跳到第i个台阶的走法
图片说明 
class Solution:
    def jumpFloor(self, number):
        # write code here
        dp = [0]*50
        dp[1] = 1
        dp[2] = 2
        for i in range(3,number+1):
            dp[i]=dp[i-1] +dp[i-2]
        return dp[number]
时间复杂度：O(n) 空间复杂度：O(n) ###继续优化 发现计算f[5]的时候只用到了f[4]和f[3], 没有用到f[2]...f[0],所以保存f[2]..f[0]是浪费了空间。 只需要用3个变量即可。 
class Solution:
    def jumpFloor(self, number):
        # write code here
        a,b,c =1,1,1
        for i in range(2,number+1):
            c = a+b
            a = b
            b = c
        return c
时间复杂度：O（n） 空间复杂度：O（1） 完美！
参考资料：