题目描述
一只青蛙一次可以跳上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