一、参考答案一起刷题吧
因为这个题目过于简单，这里直接给出参考答案：
F = [0, 1, 1]
for i in range(28):
F.append(F[-1] + F[-2])
class Solution:
def fib(self, n: int) -> int:
if not n:
return 0
return F[n]
当然也可以采用递归的写法。这里主要想介绍Python中functools下比较常用的装饰器：
@functools.lru_cache(user_function)
@functools.lru_cache(maxsize=128, typed=False)
functools.lru_cache，首先，它是一个装饰器，主是作用是减少重复计算，即当函数的参数重复时，则直接采用原来计算好的结果。因此可以看出，它底层判断重复，是通过函数的参数。因此我们需要注意，它是使用dict来做缓存，因此函数的位置参数和关键字参数必须是可哈希的。
它是一个非常实用的装饰器，实现了备忘的功能，可以将耗时的结果存储起来，避免传入相同的参数时重复计算。同时需要注意的，它也可以接受一个自定的func，只要是可调用的即可。
示例（来自官方文档）：
@lru_cache(maxsize=32)
def get_pep(num):
'Retrieve text of a Python Enhancement Proposal'
resource = 'http://www.python.org/dev/peps/pep-%04d/' % num
try:
with urllib.request.urlopen(resource) as s:
return s.read()
except urllib.error.HTTPError:
return 'Not Found'
>>> for n in 8, 290, 308, 320, 8, 218, 320, 279, 289, 320, 9991:
... pep = get_pep(n)
... print(n, len(pep))
>>> get_pep.cache_info()
CacheInfo(hits=3, misses=8, maxsize=32, currsize=8)
当不指定maxsize，即值为None时，缓存大小是没有边界的（在生产环境下是很危险的，很容易OOM），示例如下：
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
>>> [fib(n) for n in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
>>> fib.cache_info()
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)
- 缓存淘汰策略
- 如何自己实现一个lru算法
- 你用过哪些Python装饰器
