10.2.青蛙跳台阶*
题目描述*
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1
提示*
0 <= n <= 100
代码*
n 级台阶可以由 n-1 阶一步或 n-2 阶两步走到，和斐波那契一样。
如果改成一次可以跳 1 ~ n 级，那么 f(n) = 2^(n - 1)
class Solution {
public:
int numWays(int n) {
if(n == 0) {
return 1;
}
if(n <= 2) {
return n;
}
int n1 = 1, n2 = 2;
int res = 0;
while(n-- >= 3){
res = (n1 + n2)%1000000007;
n1 = n2;
n2 = res;
}
return res;
}
};
最后更新: July 23, 2022