题目：https://www.nowcoder.com/ta/coding-interviews?page=1

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

理解：

跟之前的分析有相似的地方，假设跳n级台阶有F(n)种方式，那么可能的情况有，先跳1级、或者先跳2级、或者先跳4级、…、或者先跳n-1级、或者直接跳到n级.

相应的：先跳1级后有F(n-1)种，先跳2级后有F(n-2)种，…，跳n-1级有F(1)种，值得注意的是直接跳到n级台阶为1种

于是：F(n)=F(n-1)+F(n-2)+F(n-3)+…+F(3)+F(2)+F(1)+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution1:
    def jumpFloorII(self, number):
        a = [1,2]
        if number <= 0:
            return 0
        elif number == 1:
            return 1
        elif number == 2:
            return 2
        else:
            for i in range(2, number):#i仅仅代表需要操作的次数
                ai = 1 + sum(a)
                a.append(ai)
            return a[number-1]#索引值（从0开始）比实际台阶数小1
1
2
3
method = Solution1()
answer = method.jumpFloorII(5)
answer
16

根据递推公式：$F(n)=2^{(n-1)}$

1
2
3
4
5
6
class Solution2:
    def jumpFloorII(self, number):
        if number <= 0:
            return 0
        else:
            return 2**(number-1)
1
2
3
method = Solution2()
answer = method.jumpFloorII(5)
answer
16
1
2