一、题目描述

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

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

示例 1:

输入:n = 2
输出:2

示例 2:

输入:n = 7
输出:21

示例 3:

输入:n = 0
输出:1

提示:

  • 0 <= n <= 100

二、保姆级参考代码

// 登录 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;
    }
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。