LeetCode 青蛙跳台阶问题 [简单]
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
提示：
0 <= n <= 100
题目分析
此题目和斐波那契数列一致
解法1
递归 但是会超时
解法2
迭代求解
解法3
动态求解
代码实现
public class NumWays {
public static void main(String[] args) {
System.out.println(numWays(7));
System.out.println(numWays(7));
}
public static int numWays2(int n) {
if (n == 0 || n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int one = 1;
int two = 2;
int temp;
for (int i = 3; i <= n; i++) {
temp = two;
one = (int) ((one + two) % (1e9 + 7));
two = one;
one = temp;
}
return two;
}
public static int numWays(int n) {
if (n == 0 || n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int[] res = new int[n + 1];
res[1] = 1;
res[2] = 2;
for (int i = 3; i <= n; i++) {
res[i] = (int) ((res[i - 1] + res[i - 2]) % (1e9 + 7));
}
return res[n];
}
}
