大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 专栏,在这个专栏里我将和大家一起学习如何用合理的思维来思考、解题、写代码。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题10- II. 青蛙跳台阶问题

题目链接:https://www.algomooc.com/hi-offer

一、题目描述

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

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2

示例 2:

输入:n = 7
输出:21

示例 3:

输入:n = 0
输出:1

提示:

  • 0 <= n <= 100

二、题目解析

我们依旧用 四步分析法 来分析一下这道题目。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

当有 0 级台阶时,青蛙只有一种方式可以选择,即原地不动

面试题10- II. 青蛙跳台阶问题.002

当有 1 级台阶时,青蛙只有一种方式可以选择,即从原地跳到第 1 级台阶的位置。

面试题10- II. 青蛙跳台阶问题.003

当有 2 级台阶时,青蛙有两种方式可以选择:

  • 1、从原地直接跳到 2 级台阶
  • 2、从原地跳到 1 级台阶,跳到 2 级台阶,每次只跳 1 级的高度

面试题10- II. 青蛙跳台阶问题.004

当有 3 级台阶时,青蛙以下方式可以选择:

  • 1、先从原地跳到 1 级台阶,再从 1 级台阶想办法跳到 3 级台阶,通过上述 2 级台阶的情况分析可知,后者的选择方式有两种
  • 2、先从原地跳到 2 级台阶,再跳 1 级的高度到达 3 级台阶

通过分析可得,当有 3 级台阶时,青蛙有三种方式可以选择。

面试题10- II. 青蛙跳台阶问题.005

……

当有 n 级台阶时,青蛙以下方式可以选择到达 n 级台阶的位置:

  • 1、从 n-2 级台阶跳两次,每次只跳 1 级的高度到达 n 级台阶
  • 2、从 n-1 级台阶跳一次,每次只跳 1 级的高度到达 n 级台阶

面试题10- II. 青蛙跳台阶问题.006

2、规律

无论有多少级台阶,青蛙到最后都面临两种情况:要么跳 1 级台阶的高度,要么跳 2 级台阶的高度

面试题10- II. 青蛙跳台阶问题.007

所以如果我们假设跳上 n 级台阶总计有 f(n) 种跳法,那么跳到 n – 2 级台阶有 f(n-2) 种跳法,跳到 n – 1 级台阶有 f(n-1) 种跳法。

到达 n 级台阶时要么是从 n – 1 级跳上来,要么是从 n – 2 级跳上来,所以 f(n) = f(n-2) + f(n-1)

是不是很熟悉的感觉?

这道题目和上篇 剑指 offer 10- I. 斐波那契数列 类似,只不过它们的起始值不一样而已。

斐波那契数列问题中,f(0) = 0,f(1) = 1,f(2) = 1。

而在青蛙跳台阶问题中,f(0) = 1,f(1) = 1,f(2) = 2。

这里吐槽一下,没有台阶的情况下,青蛙的选择方式居然为 1 ,感觉充满着哲学气息:没有选择也是一种选择?!

3、匹配

新建一个长度为 n + 1 的数组,用于在递归时存储 f(0) 到 f(n) 的值,重复遇到某数字时则直接从数组取用,避免大量重复的递归计算。

4、边界

  • 1、没有台阶
  • 2、只有一级台阶

三、动画理解

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、参考代码

// 访问 AlgoMooc 官网,获取更多题解:https://www.algomooc.com
class Solution {
    public int numWays(int n) {
        // 新建一个长度为 n+1 的数组,用于在递归时存储 memo(0) 到 memo(n) 的值,重复遇到某数字时则直接从数组取用,避免大量重复的递归计算。例如 memo[0]表示从第 0 级跳到第 n 级的方式数量
        long memo[] = new long[n + 1];
        // 得到从第 0 级跳到第 n 级的方式数量
        return (int) helper(0, n, memo);
    }
    public long helper(int i, int n, long memo[]) {

        if (i > n) { // 边界处理
            return 0;
        }

        if (i == n) { // 相当于原地起跳,只有一种方式
            return 1;
        }
        if (memo[i] > 0) { // 数组中存储了结果,直接拿来用
            return memo[i];
        }
        // 无论有多少级台阶,青蛙到最后都面临两种情况:要么跳 1 级台阶的高度,要么跳 2 级台阶的高度。
        // 假设跳上 n 级台阶总计有 memo(n) 种跳法,那么跳到 n - 2 级台阶有 memo(n-2) 种跳法,跳到 n - 1  级台阶有 memo(n-1) 种跳法,并且  memo(n) = memo(n-2) + memo(n-1)。
        // memo[i]表示从第 i 级跳到第 n 级的方式数量
        memo[i] = helper(i + 1, n, memo) + helper(i + 2, n, memo);

        // 取模返回结果
        return memo[i] % 1000000007;
    }
}

五、复杂度分析

时间复杂度

时间复杂度为 O(N) 。

空间复杂度

空间复杂度为 O(N)。

六、相关标签

  • 递归
  • 记忆化
  • 备忘录
  • 动态规划

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(1)