10-Ⅱ 青蛙跳台阶问题

Lin2J
2021-07-21 / 0 评论 / 86 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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)$:使用常数级的空间。