解题思路

首先想到这可能是一个排列组合的问题，青蛙每次只能跳1或者2级，假设跳2级的次数为a，那么当a=0时，只有1种跳法，当a=1时，某两个台阶合并为一次，其他台阶都跳一次，这就成了一个组合问题，此时的跳法有C(n-1, 1)种，当a=2时，跳法有C(n-2, 2)种。然后要考虑a有多少种取值，显然，a = n/2，然后就可以根据公式求解：t = C(n, 0) + C(n-1, 1) + ... + C(n-a, a)
青蛙每次只能跳1级或者2级，那么就只需要考虑两个可能：（1）第一次跳1级，那么剩下的就是F(n-1)种跳法；（2）第一次跳2级，那么剩下的就是F(n-2)种跳法。总的跳法F(n) = F(n-1) + F(n-2)，就是一个斐波那契数列。

实现

python

排列组合公式：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        num2 = int(number/2)
        time = 1
        for i in range(1, num2+1):
            d = 1
            n = 0
            num = number - i
            u = 1
            while n0:
                u = u*num
                num -= 1
                n -= 1
            time += int(u/d)
        return time

斐波那契数列（和前面的斐波那契数列解法相同）：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number<=2:
            return number
        a = 1
        b = 2
        for i in range(number-2):
            b = a + b
            a = b - a
        return b

补充

刚开始的时候看错了题目，看成了青蛙也可以跳n级，好不容易解出来发现结果不通过。虽然题目理解有误，但还是找出了解法，就当看作是扩展练习吧。

题目的错误理解：一只青蛙一次可以跳上1级台阶，也可以跳上2级，… ，也可以跳上n级（也就是可以跳任意级）。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解题思路

青蛙第一次跳1阶，剩下的跳法就有F(n-1)种；青蛙第一次跳2阶，剩下有F(n-2)种跳法；…；青蛙第一次跳n-1阶，剩下有F(1)种跳法；最后青蛙一次跳n阶，剩下的跳法是F(0)。总的跳法F(n) = F(n-1) + F(n-2) + ... + F(1) + F(0)，可以用递归来实现（这种想法时间复杂度太高）。
按上面的想法实现复杂度太高，然后想了一下，F(n) = F(n-1) + F(n-2) + ... + F(0)，F(n-1) = F(n-2) + ... + F(0)，发现F(n) = F(n-1) * 2，问题一下就简单多了。

实现

Python

方法一（复杂度高）：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 0:
            return 1
        time = 0
        n = number
        while n:
            n -= 1
            time += self.jumpFloor(n)
        return time

方法二：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number <= 1:
            return 1
        return self.jumpFloor(number-1)*2