剑指 Offer 10- II. 青蛙跳台阶问题

题目描述

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

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

示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1
提示：

0 <= n <= 100

解题思路

使用动态规划。想跳到第n个台阶上，要么是从第n-1个台阶跳一步上去，要么是从第n-2个台阶跳两步上去。因此dp[n] = dp[n-1] + dp[n-2]。
状态定义：dp[n]为跳第n个台阶
转移方程：dp[n] = dp[n-1] + dp[n-2]
初始状态：dp[0] = [1] dp[1] = 1
返回值：int(dp[n] % 1000000007)

解题代码

class Solution:
    def numWays(self, n: int) -> int:
        dp = [1, 1]
        if n < 2:
            return dp[n]
        for i in range(2, n + 1):
            step = dp[i-2] + dp[i-1]
            dp.append(step)
        return int(dp[n] % 1000000007)

执行结果

执行结果：通过
执行用时：32 ms, 在所有 Python3 提交中击败了94.28%的用户
内存消耗：14.9 MB, 在所有 Python3 提交中击败了22.41%的用户