10-Ⅱ 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题

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