[每日一题] 第十七题：青蛙跳台阶问题
0 / 0 / 创建于 4年前
DRose 的个人博客
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
提示：
0 <= n <= 100
题解
方法一：我的做法
本题很容易看出是递归方法来，同斐波那契数列很相似。
这里我列出几个注意事项：
- F(0)=1，F(1)=1
- F(N) = F(N-1) + F(N-2)
- 要把之前的结果保存下来，这样就不会重复计算
- 答案一定记得要取模，不然无法通过
代码
class Solution {
public int numWays(int n) {
if (n <= 1) {
return 1;
}
int[] nums = new int[n+1];
nums[0] = 1;
nums[1] = 1;
int current = 2;
while (current <= n) {
nums[current] = (nums[current-1] + nums[current-2]) % 1000000007;
current++;
}
return nums[n];
}
}
复杂度
时间复杂度 O(N)：计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。
空间复杂度 O(N)：因为新创建了个 nums 数组，需要额外的 N 个空间
方法二：动态规范
解题思路：
此类求多少种可能性的题目一般都有 递推性质，即 f(n) 和 f(n-1) …… f(1) 之间是有联系的。
设跳上 n 级台阶有 f(n) 种跳法，在所有跳法中，青蛙的最后一步只有两种情况，跳上 1 级或 2 级台阶。
- 当为 1 级台阶： 剩 n - 1 个台阶，此情况共有 f(n-1) 种跳法；
- 当为 2 级台阶： 剩 n - 2 个台阶，此情况共有 f(n-2) 种跳法。
f(n) 为以上两种情况之和，即
f(n) = f(n-1) + f(n-2)，以上递推性质为斐波那契数列。本题可转化为求斐波那契数列第 n 项的值，但起始数字不同。- 青蛙跳台阶问题：f(0)=1，f(1)=1，f(2)=2
- 斐波那契数列问题：f(0)=0，f(1)=1，f(2)=1
![[每日一题] 第十七题：青蛙跳台阶问题](https://cdn.learnku.com/uploads/images/202007/31/61979/2E1KK0kRBv.png!large)
斐波那契数列的定义是 f(n + 1) = f(n) + f(n - 1) ，生成第 n 项的做法有以下几种：
- 递归法：
原理： 把 f(n) 问题的计算拆分成 f(n−1) 和 f(n−2) 两个子问题的计算，并递归，以 f(0) 和 f(1) 为终止条件。
缺点： 大量重复的递归计算，例如 f(n) 和 f(n−1) 两者向下递归都需要计算 f(n−2) 的值。- 记忆化递归法：
原理： 在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 f(n) 的数字值，重复遇到某数字时则直接从数组取用，避免了重复的递归计算。
缺点： 记忆化存储的数组需要使用 O(N) 的额外空间。- 动态规划：
原理： 以斐波那契数列性质 f(n+1)=f(n)+f(n−1) 为转移方程。
从计算效率、空间复杂度上看，动态规划是本题的最佳解法。
动态规划解析：
- 状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表
斐波那切数列第 i 个数字。 - 转移方程： dp[i+1] = dp[i] + dp[i-1]，即对应数列定义 f(n+1)=f(n)+f(n-1)；
- 初始状态： dp[0] = 1，dp[1] = 1，即初始化前两个数字；
- 返回值： dp[n]，即斐波那切数列第 n 个数字。
空间复杂度优化：
若新建长度为 n 的 dp 列表，则空间复杂度为 O(N)。
- 由于 dp 列表第 i 项只与第 i-1 和 第 i-2 项有关，因此只需要初始化三个整形变量，
sum，a，b，利用辅助变量 sum 使 a，b两数字交替前进即可（具体实现见代码）。 - 因为节省了 dp 列表空间，因此空间复杂度降至 O(1)。
循环求余法：
大数越界，随着 n 增大，f(n) 会超过
Int32甚至Int64的取值范围，导致最终的返回值错误。
求余运算规则： 设正整数 x，y，p，求余符号为 ⊙ ，则有 (x+y)⊙p=(x⊙p+y⊙p)⊙p 。
解析： 根据以上规则，可推出 f(n)⊙p = [f(n−1)⊙p+f(n−2)⊙p]⊙p ，从而可以在循环过程中每次计算 sum=a+b⊙1000000007 ，此操作与最终返回前取余等价。
复杂度：
时间复杂度 O(N)：计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。
空间复杂度 O(1)：几个标志变量使用常数大小的额外空间。
解法来源
作者：jyd
链接：leetcode-cn.com/problems/qing-wa-t...
来源：力扣（LeetCode）
来源
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/qing-wa-t...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号