【題目描述】
大家都知道斐波那契數(shù)列翰意,現(xiàn)在要求輸入一個整數(shù)n盗舰,請你輸出斐波那契數(shù)列的第n項蕊程。
n<=39
【思路】
遞歸:超時
迭代:可行
【代碼】
class Solution:
def Fibonacci(self, n):
# write code here
'''def compute_Fibonacci(x):
if x==0:
return 0
elif x==1:
return 1
else:
return compute_Fibonacci(x-1)+compute_Fibonacci(x-2)
return compute_Fibonacci(n)'''
if n==0:
return 0
if n==1:
return 1
res = [0,1]
for i in range(2,n+1):
res.append(res[i-1]+res[i-2])
return res[n]