LeetCode题解—青蛙跳台阶
今天聊个经典题目：青蛙跳台阶问题
题目
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：输入：n = 2 输出：2
示例 2：输入：n = 7 输出：21
题解
假设 n 级的台阶共有f(n)种跳法，那么共有两种情况可以跳到第n级：
- 1、在
n-1级台阶地方，跳一步到n级台阶 - 2、在
n-2级台阶地方，跳两步到n级台阶
所以得出， f(n) = f(n-1) + f(n-2)。
所以这题其实就是一道斐波那契数列。
斐波那契数列我们就熟悉了啊，之前专门写过一篇。
我们可以得出第一种解法：递归
解法1
public int numWays(int n) {
if(n==0)return 1;
if(n<3)return n;
int first=numWays(n-1) % 1000000007;
int second=numWays(n-2)% 1000000007;
return (first+second)% 1000000007;
}
还是老问题，这种递归会有大量重复计算。
比如f(5)=f(4)+f(3)，f(4)=f(3)+f(2)，f(3)计算了两次。
所以我们将它优化下，对于已经计算过的数值存储起来。
解法2
记忆化递归方法，用数组memo存储已经计算过的数值。
class Solution {
private int[] memo;
public int numWays(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
return jump(n);
}
private int jump(int n) {
if (memo[n] != -1) {
return memo[n];
}
if (n == 1 || n == 0) {
return 1;
}
memo[n] = (jump(n - 1) + jump(n - 2)) % 1000000007;
return memo[n];
}
}
时间复杂度
O(n)
空间复杂度
O(n)
解法3
有没有更好的解法呢？可以发现在这个问题中，每次计算得出的结果又可以被下一个台阶所利用，并得出新的结果。
比如f(5)要用到f(4)和f(3)的结果，f(4)又可以被f(6)所利用。
这种大问题可以被解析成小问题，并且小问题的结果可以被重复调用的情况，就可以用到 动态规划算法。
还是贯彻f(n) = f(n-1) + f(n-2)的公式，用一个数组进行存储结果，可以得出初步的动态规划解法：
public int numWays(int n) {
if (n == 0 || n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i - 2] + dp[i - 1]) % 1000_000_007;
}
return dp[n];
}
时间复杂度
O(n)
空间复杂度
O(n)
解法4
还能不能优化呢？
其实这个数组可以不用，使用两个变量存储结果，每次存储新的结果就可以，因为每次都只需要上两个结果。
public int numWays(int n) {
if (n == 0 || n == 1) {
return 1;
}
int pre = 1, cur = 2;
for (int i = 3; i <= n; i++) {
int tmp = (pre + cur) % 1000_000_007;
pre = cur;
cur = tmp;
}
return cur;
}
用pre和cur两个变量代替了之前的数组dp，每次计算完下一个值之后，也就是tmp=pre+cur。
再次对pre和cur重新赋值，如此反复，最终完成计算。
这种解法的空间复杂度就能优化为O(1)。
参考
https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
感谢大家的阅读，有一起学习的小伙伴可以关注下公众号—
码上积木❤️ 每日一个知识点，建立完整体系架构。
腾讯云开发者
