一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
解题思路:
设跳上 $n$ 级台阶可能有 $f(n)$ 中可能性,当青蛙跳到最后的时候,会有两种情况,一种是跳 $1$ 级,一种是跳 $2$ 级。
- 当为 $1$ 级的时候,剩下的 $n-1$ 级台阶有 $f(n-1)$ 种跳法。
- 当为 $2$ 级的时候,剩下的 $n-2$ 级台阶有 $f(n-2)$ 种跳法。
因此很容易得到递推式
$$
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$。
因此可以使用动态规划来接题。
代码:
public int numWays(int n) {
if (n == 0 || n == 1) {
return 1;
}
int a = 1;
int b = 1;
int sum = 0;
while(--n > 0){
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return sum;
}
复杂度分析
-
时间复杂度$O(N)$:需要进行 $N$ 次循环,每次循环的操作是 $O(1)$ 的。
-
空间复杂度$O(1)$:使用常数级的空间。
评论区