一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。
求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1

>本题目是个动态规划问题，只需要找到转移方程
>我们想象青蛙跳最后一次时，会有两种跳法
>一种是跳1阶，另外一种是跳2阶
>在跳1阶这种情况下，青蛙已经跳了n-1阶，那他前n-1阶跳法就是f(n-1)
>对应2阶的情况下，青蛙跳了n-2阶，那他前n-2阶跳法就是f(n-2)
>所以对应总共n阶情况就是两种情况的加和
>f(n)=f(n-1)+f(n-2)
>这就转化成了斐波那契数列，但是本问题中f(0)=1,f(1)=1

class Solution:
    def numWays(self, n: int) -> int:
        if n<=1:
            return 1
        else:
            first=1
            second=1
            for i in range(n-1):
                temp=first
                first=second
                second=(second+temp)%(1e9+7)
            return int(second)

class Solution {
    public int numWays(int n) {
        if(n<=1) {
      return 1;
    }
    else {
      double first=1;
      double second=1;
      for(int i=0;i<n-1;i++) {
        double temp=first;
        first=second;
        second=(second+temp)%(1e9+7);
      }
      return (int)second;
    }
    }
}