lc-青蛙跳台阶 Posted on 2020-02-24 In leetcode 题目:青蛙跳台阶 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 1234567891011示例 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 代码 1234567891011121314object 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 } }}