今天聊个经典题目:青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:输入:n = 2 输出:2
示例 2:输入:n = 7 输出:21
假设 n
级的台阶共有f(n)
种跳法,那么共有两种情况可以跳到第n级:
n-1
级台阶地方,跳一步到n级台阶n-2
级台阶地方,跳两步到n级台阶所以得出, f(n) = f(n-1) + f(n-2)。
所以这题其实就是一道斐波那契数列。
斐波那契数列我们就熟悉了啊,之前专门写过一篇。
我们可以得出第一种解法:递归
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)
计算了两次。
所以我们将它优化下,对于已经计算过的数值存储起来。
记忆化递归方法,用数组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)
有没有更好的解法呢?可以发现在这个问题中,每次计算得出的结果又可以被下一个台阶所利用,并得出新的结果。
比如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)
还能不能优化呢?
其实这个数组可以不用,使用两个变量存储结果,每次存储新的结果就可以,因为每次都只需要上两个结果。
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/
感谢大家的阅读,有一起学习的小伙伴可以关注下公众号—
码上积木
❤️ 每日一个知识点,建立完整体系架构。