题目难度: 简单

原题链接

今天继续更新剑指 offer 系列, 这道题同样是一道经典题目, 而且跟昨天的题目很接近, 不同的地方在于这道题需要自己进行抽象, 而不是直接给出转移方程 😂 同样这道题也有空间上的一些优化, 值得注意

若无意外, 每天晚上 6 点 45 分准时更新, 中间可能会穿插一些周赛题解. 大家在我的公众号"每日精选算法题"中的聊天框中回复 offer 就能看到该系列当前已经更新的文章了

大家有什么想法建议和反馈的话欢迎随时交流, 包括但不限于公众号聊天框/知乎私信评论等等~

题目描述

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

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

0 <= n <= 100

题目样例

示例 1

输入

2

输出

2

示例 2

输入

7

输出

21

题目思考

  1. 第 n 阶台阶的跳法数目可以根据什么得出?

解决方案

思路

分析

  • 分析题目, 每次要么跳 1 级, 要么跳 2 级, 也就是相邻台阶之间的关系非常明确, 可以尝试动态规划的思路
  • 转移方程: 对于第 n 阶台阶来说, 它可以从 n-1 阶跳 1 级得到, 也可以由 n-2 阶跳 2 级得到, 这两种方案由于倒数第二阶不相同, 所以没有任何重合部分, 自然第 n 阶的跳法数目就是 n-1 阶和 n-2 阶的跳法数之和了
  • 初始化: 因为用到了n-1 和 n-2, 所以初始化需要考虑 0 和 1. 如果有 0 阶台阶, 那么只能不跳, 有 1 种方案; 如果有 1 阶台阶, 只能选择跳 1 级, 也是 1 种方案. 这样第 2 阶就是 1+1=2 种方案了, 就是对应于跳 1 级或者跳 2 级这两种

实现

  • 定义 dp 数组, 初始化dp[0] = 1, dp[1] = 1
  • 然后从 2 开始循环直到 n, 每次套用dp[n] = dp[n-1] + dp[n-2] 即可
  • 特别注意根据题目要求, 每次相加得到新的 dp 值时需要取模 (如果最后结果再取模的话, 对于 python 而言由于涉及大数操作, 速度会慢一些, 而对于 C/Java 等语言的话则可能会导致溢出)
  • 优化
    • 注意到当前 dp 值只和前面两个 dp 值有关, 所以我们同样可以只使用两个变量 pre 和 prepre, 分别代表当前下标的前一个和再上一个下标的 dp 值 dp[n-1] 和 dp[n-2].
    • 然后当前的 dp 值就更新为它们两个的和
    • 最后更新当前 dp 值为新的 pre, 原来的 pre 就是新的 prepre 了
    • 而最终结果就是 pre 了, 因为遍历完 n 之后, 当前 dp 值已经更新为 pre 了

复杂度

  • 时间复杂度 O(N)
    • 需要遍历整个数组一遍
  • 空间复杂度 O(1)
    • 优化后只需要几个变量即可

代码

class Solution:
    def numWays(self, n: int) -> int:
        if n <= 1:
            # 第0阶和第1阶都只有1种跳法
            return 1
        # 初始化0和1阶的跳法数目
        prepre, pre = 1, 1
        for i in range(2, n + 1):
            # 从3阶开始循环, 它可以有第2阶跳1级得到, 也可以由第1阶跳2级得到, 所以当前dp值就等于prepre + pre
            prepre, pre = pre, (prepre + pre) % 1000000007
        return pre

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊

每日精选算法题 - 微信扫一扫关注我