题目
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
python代码
class Solution(object):
def __init__(self):
self._a = 10**9+7
def fib(self, n):
if n<=1:
return n
f0 = 0
f1 = 1
f_sum = 0
for i in range(n-1):
f_sum = f0+f1
f0,f1 = f1,f_sum
return f_sum%self._a
上述代码直接从斐波那契数列的定义出发，逐步求出所需的值。
class Solution(object):
def __init__(self):
self._a = 10**9+7
def fib(self, n):
if n<=1:
return n
return self.fib(n-1)+self.fib(n-2)
当然我们还可以使用递归，因为斐波那契数列的特殊规律，可以很简洁的构造出递归结构（注意：上述的递归代码在leetcode中判定为超时）
拓展
这道题考察的比较常规，无论是直接法还是递归法都是容易想到的。在后面重刷时无意间看到别人分享的代码，发现了一个有趣的做法，使递归在leetcode的判定系统中顺利通过
class Solution:
from functools import lru_cache
@lru_cache(None)
def fib(self, n: int) -> int:
if n<=1:
return n
return (self.fib(n-1)+self.fib(n-2))%1000000007
- 代码需要在Python3中运行
- 使用了lru_cache修饰器，它减少了fib函数计算的次数，当fib遇到之前计算过得值时，直接从缓存取值。
lru_cache
python 标准库中的 functools.lru_cache 装饰器实现了一个 LRU 算法的缓存，用来缓存方法所有参数与返回值的对应关系，用来提升一个方法频繁用相同参数调用场景下的性能。
比如对于fib(4)，我们需要计算fib(0)两次，fib(1)三次，fib(2)两次，fib(3)一次，当n更大时，重复计算的项也会增加，相同项重复的次数也会增加，所以lru_cache装饰器就是将之前计算过得函数输出缓存下来，当后面再次遇到相同的输入值时，直接从缓存区拿出对应的函数输出。当使用lru_cache后，再去计算fib(4)，我们实际g只需计算fib(0)、fib(1)、fib(2)、fib(3)各一次即可。