题目描述
大家都知道斐波那契数列，现在要求输入一个整数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)
