递归法

我们定义问题为f(n)，那么由题目信息可知，f(n) = f(n - 1) + .. + f(2) + f(1)。递归的终止条件为n 为 0的时候，我们返回1。

你可以使用记忆化递归优化运行时间

代码:

class Solution:
    def jumpFloorII(self, number):
        if number == 0:
            return 1
        cnt = 0
        for i in range(number):
            cnt += self.jumpFloorII(i)
        return cnt

复杂度分析

• 时间复杂度：我们可以想象成组合，由排列组合原理知道组合数为2^(number)，故时间复杂度为
• 空间复杂度：空间复杂度取决于栈深度，因此空间复杂度

数学法

由于f(n) = f(n - 1) + .. + f(2) + f(1), 那么我们容易得出f(n - 1) = f(n - 2) + .. + f(2) + f(1) 。将后者代入前者，我们得到：f(n) = f(n - 1) + f(n - 1),即f(n) = 2 * f(n - 1)，这是一个等比数列，因此直接使用等比数列的通项公式aq^(n - 1)即可,在本题中a（首项）为1，q为2（公比）。

代码:

class Solution:
    def jumpFloorII(self, number):
        return 2 ** (number - 1)

复杂度分析

• 时间复杂度：
• 空间复杂度:

欢迎关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解