剑指offer之008-跳台阶

题目描述

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

关于明柳梦少

坚守自己的原则,不随波逐流。