青蛙跳台阶问题
问题描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
解题思路
动态规划
- 青蛙想到第
X级台阶，只存在两种可能，从第X-1级台阶处跳1级，从第X-2级台阶处跳2级。假设f(x)表示青蛙跳到第X级台阶的总跳法，则其等于f(x-1) + f(x-2)，其中x >= 2，且f(0) = 1, f(1) = 1 - 时间复杂度：
O(n)，空间复杂度：O(1)
class Solution {
public int numWays(int n) {
int first = 1, second = 1, Mod = 1_000_000_007;
for (int i = 0; i < n; ++i) {
int third = (first + second) % Mod;
first = second;
second = third;
}
return first;
}
}
