本文共 751 字，大约阅读时间需要 2 分钟。

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

经典的跳台阶问题是青蛙一次只能上1级台阶或者2级台阶，此时对于一个n级的台阶，如果青蛙先跳1级，则剩下的n-1级可以有f(n-1)中跳法；如果青蛙先跳2级，则剩下的n-2级可以有f(n-2)种跳法，因此可以总结f(n) = f(n-1)+f(n-2)，即斐波拉契数列。

将该思想运用到拓展问题上，则可以有f(n) = f(n-1) + f(n-2) +... + f(1) + 1

此时可以用累加的方法

# -*- coding:utf-8 -*-class Solution:    def jumpFloorII(self, number):        # write code here        f1 = 1        if number == 1:            return 1        else:            for i in range(number-1):                f1 += f1            return f1

如果对应原公式写出几个具体的数就可以发现规律：

1，2，4，8，16...

即

或者可以理解为：青蛙前方一共有n级台阶，最后一级是要达到的，其他的n-1级都可以选择跳或不跳，因此也就是

这种可以称之为数学归纳法（就挺暴力的....）

# -*- coding:utf-8 -*-class Solution:    def jumpFloorII(self, number):        # write code here        return 2**(number-1)

转载地址：https://blog.csdn.net/sinat_42437278/article/details/117380973 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！