本文共 772 字，大约阅读时间需要 2 分钟。

为了解决这个问题，我们需要计算一只青蛙跳上 n 级台阶的总方法数。青蛙可以每次跳 1 级或者 2 级台阶。我们需要找到所有可能的跳法，并对结果取模 1e9+7。

方法思路

这个问题可以通过动态规划来解决。我们可以利用斐波那契数列的特性来简化计算，因为每次跳台阶的方法数等于前一次跳 1 级和前一次跳 2 级的方法数之和。

具体步骤如下：

解决代码

int numWays(int n) {    const int mod = 1e9 + 7;    if (n < 2) return 1;    if (n == 2) return 2;    int x = 1, y = 2;    for (int i = 3; i <= n; ++i) {        int tmp = y;        y = (x + y) % mod;        x = tmp;    }    return y;}

代码解释

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常高效。

转载地址：http://rbgfk.baihongyu.com/