0%

lc-青蛙跳台阶

Posted on In

题目：青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

1
2
3
4
5
6
7
8
9
10
11
示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
提示：

0 <= n <= 100

思路

考虑最后一个台阶n，有两种方式达到n，一是从n-2跳过去，一是从n-1跳过去。

因此：

  • f(n) = f(n-1) + f(n-2)
  • 条件：n>1

其中:

  • f(0) = f(1) = 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
object Solution {
    def numWays(n: Int): Int = {
        if(n<2) return 1
        else{
            var (a,b,sum)=(1,1,0)
            for(i <- 2 to n){
                sum = (a+b)%1000000007
                a = b 
                b = sum
            }
            sum
        }
    }
}