剑指Offer 7：斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

常见的递归做法如下(以下这个做法在牛客上面过不了，可能是因为时间限制？？），可以引生出很多题目，比如青蛙跳阶问题，变态跳问题

class Solution:
    def Fibonacci(self, n):
        if n==0:
            return 0
        elif n ==1:
            return 1
        else:
            return (self.Fibonacci(n-1)+ self.Fibonacci(n-2))

斐波纳挈的非递归做法

class Solution:
    def Fibonacci(self, n):
        if n==0:
            return 0
        elif n ==1:
            return 1
        else:
            one = 0
            two = 1
            for i in range(2,n+1):
                fn = one + two
                one = two
                two = fn
            return fn

青蛙跳阶问题

一只青蛙一次可以跳上一级台阶，也可以跳上2级，求该青蛙跳上一个n级台阶总共有多少种跳法

按递归的做法
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)

青蛙变态跳阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶·····也可以跳上n级台阶，此时该青蛙跳上一个n级的台阶共有多少种跳法

这个问题，网上很多种做法来鬼出来f(n) = 2 * (n-1)
有用数学归纳法的等等等，对于我这种高中知识早就还给体育老师的人来说，·····
可以这样理解这个f(n)的式子
对于最后一节台阶，必须选择跳，其他的台阶青蛙都必须选择跳与不跳。所以是f(n) = 2*(n-1)