一只青蛙一次可以跳上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)$：使用常数级的空间。