大家好,我是程序员吴师兄,欢迎来到 图解剑指 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)。
六、相关标签
- 递归
- 记忆化
- 备忘录
- 动态规划