AlgoPressAppearance
10-II-青蛙跳台阶问题
题目描述
https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
提示：
0 <= n <= 100
注意：本题与主站 70 题相同：https://leetcode.cn/problems/climbing-stairs/
思路分析
因为 n <=100 ，所以不能用递归解法，否则会堆栈溢出
此题是斐波那契数列的变种，即：后面的情况是前面情况的叠加
- 有一级台阶 一种跳法
- 只有二级台阶 二种跳法，一种是1级跳两次，另外一种是2级跳一次
- 三级台阶时， 一种方法是先跳到1级，然后跳2级， 另一种方法先跳到2级，然后跳1次
- 多级台阶同上， 即 F(n) = F(n-1) + F(n-2)
实现代码
csharp
public class Solution {
public int NumWays(int n) {
if(n == 0){
return 1;
}
if(n <= 2){
return n;
}
int first = 1;
int second = 2;
int result = 0;
for(int i = 3; i <= n; i++){
result = (first + second) % 1000000007;
first = second;
second = result;
}
return result;
}
}