剑指Offer10-II-青蛙跳台阶问题

兴趣爱好交流 每日一题
1

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：


输入：n = 2

输出：2

示例 2：


输入：n = 7

输出：21

示例 3：


输入：n = 0

输出：1

提示：


0 <= n <= 100

解

使用动态规划，首先得出规划方程 f(n) = f(n-1) + f(n-2) ：

第 n 级台阶的跳法 = 第 n-1 级台阶的跳法再跳 1 级 + 第 n-2 级台阶的跳法再跳 2 级。


class Solution:

    def numWays(self, n: int) -> int:

        # 排除特殊情况，从 n == 3 开始计算 

        if n <= 1:

            return 1

        if n == 2:

            return 2

        a = 1

        b = 2

        result = a + b

        for i in range(n - 2):

            result = a + b

            a = b

            b = result

        return result % 1000000007
2

是这样吗？简单的递归？

def fn(n):
    if n==0:
        return 1
    elif n==1:
        return 1
    else:
        return (fn(n-1)+fn(n-2))%1000000007


print(fn(1))
4

递归一般都会超时，建议看看动态规划