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

一只青蛙一次可以跳上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

是这样吗?简单的递归?

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))

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

关闭