题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路
假设对于第n级台阶，总共有f(n)种跳法。
青蛙跳上最后一级台阶的方式只有两种情况，要么是1级跳，要么是2级跳。若青蛙用1级跳的方式跳到最后一级台阶，那么它前面跳的方法共有f(n-1)种；若用2级跳，则共有f(n-2)种。所以，两种情况加起来就是总种数：f(n) = f(n-1) + fn (n-2) （n>=2），其中f(1)=1，f(2)=2
class Solution(object):
def numWays(self,n):
if n==0:return 1
f1 = 1
f2 = 2
if n == 1:return f1
if n == 2:return f2
for _ in range(n-2):
f2 ,f1 = f1+f2,f2
return f2 % 1000000007