一只青蛙一次可以跳上1級臺階溉委，也可以跳上2級臺階。求該青蛙跳上一個 n 級的臺階總共有多少種跳法棱貌。
答案需要取模 1e9+7（1000000007）原环，如計算初始結(jié)果為：1000000008，請返回 1贿条。
示例 1：
輸入：n = 2
輸出：2
示例 2：
輸入：n = 7
輸出：21
提示：
0 <= n <= 100
注意：本題與主站 70 題相同：https://leetcode-cn.com/problems/climbing-stairs/
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
解題思路：
看過劍指offer的人應(yīng)該對這道題都有印象盈罐，那個叫做斐波那契數(shù)列其實就是這道題的核心。
科普一下下
斐波那契數(shù)列（Fibonacci sequence）闪唆，又稱黃金分割數(shù)列、兔子數(shù)列钓葫，是數(shù)學(xué)家列昂納多·斐波那契于1202年提出的數(shù)列悄蕾。
斐波那契數(shù)列為1、1、2帆调、3奠骄、5、8番刊、13含鳞、21、34……此數(shù)列從第3項開始芹务，每一項都等于前兩項之和蝉绷，遞推公式為F(n)=F(n-1)+F(n-2)，n≥3枣抱，F(xiàn)(1)=1熔吗，F(xiàn)(2)=1。
在現(xiàn)代物理佳晶、準晶體結(jié)構(gòu)桅狠、化學(xué)等領(lǐng)域，斐波納契數(shù)列都有直接的應(yīng)用轿秧，為此中跌，美國數(shù)學(xué)會從1963年起出版了以《斐波納契數(shù)列季刊》為名的一份數(shù)學(xué)雜志，用于專門刊載這方面的研究成果菇篡。
主要利用的公式就是斐波那契公式的變種F(n)=F(n-1)+F(n-2)漩符，n≥3，F(xiàn)(1)=1逸贾，F(xiàn)(2)=2
同樣很正吃山觯可以想到遞歸，遞歸是可以實現(xiàn)的铝侵，但確實執(zhí)行時間過長灼伤，leetcode網(wǎng)站不接受，所以在此就忽略了咪鲜。
看非遞歸算法狐赡，也就是循環(huán)求的F(1), F(2), F(3) ... F(n), 再把結(jié)果累計下來就是總數(shù)
public int numWays(int n) {
if (n<0)
return 0;
if (n==1 || n==0)
return 1;
if (n==2)
return 2;
int step = 0;
int fn1 = 1, fn2 = 2;
int m = 1000000007;
for(int i=2; i<n; i++){
step = (fn1 + fn2)%m;
fn1 = fn2;
fn2 = step;
}
return step;
}
10-I 斐波那契數(shù)列解法相同
