大家好，我是程序员吴师兄，欢迎来到 图解剑指 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 级台阶时，青蛙只有一种方式可以选择，即原地不动。
当有 1 级台阶时，青蛙只有一种方式可以选择，即从原地跳到第 1 级台阶的位置。
当有 2 级台阶时，青蛙有两种方式可以选择：
- 1、从原地直接跳到 2 级台阶
- 2、从原地先跳到 1 级台阶，再跳到 2 级台阶，每次只跳 1 级的高度
当有 3 级台阶时，青蛙以下方式可以选择：
- 1、先从原地跳到 1 级台阶，再从 1 级台阶想办法跳到 3 级台阶，通过上述 2 级台阶的情况分析可知，后者的选择方式有两种
- 2、先从原地跳到 2 级台阶，再跳 1 级的高度到达 3 级台阶
通过分析可得，当有 3 级台阶时，青蛙有三种方式可以选择。
……
当有 n 级台阶时，青蛙以下方式可以选择到达 n 级台阶的位置：
- 1、从 n-2 级台阶跳两次，每次只跳 1 级的高度到达 n 级台阶
- 2、从 n-1 级台阶跳一次，每次只跳 1 级的高度到达 n 级台阶
2、规律
无论有多少级台阶，青蛙到最后都面临两种情况：要么跳 1 级台阶的高度，要么跳 2 级台阶的高度。
所以如果我们假设跳上 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、只有一级台阶
三、动画理解
此处内容需要权限查看
会员免费查看四、参考代码
// 访问 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)。
六、相关标签
- 递归
- 记忆化
- 备忘录
- 动态规划
