本文首发于我的个人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/03/target-offer-fibonacci-sequence.html 作者: Suixin
斐波那契数列
注：不是斐波那契数列的第一项，而是第零项。
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
解题思路
只需注意斐波那契数列的第零项即可。
代码
Python(2.7.3)
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
a = [1, 1]
if n < 0:
return
elif n == 0:
return 0
else:
length = 2
while length < n:
a.append(a[-1] + a[-2])
length += 1
return a[n - 1]
运行时间：27ms
占用内存：5756k
注：实现斐波那契数列不一定需要使用列表，只是使用列表可以把数列完全存储下来，如果只需要某一项的值，完全可以：
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
