实现斐波拉契数列
方法一（递归）
from functools import lru_cache
# 递归
class Solution:
@lru_cache(10**8)
def climbStairs(self, n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
使用递归的方法比较明显简单，可是如果要求的数过大的话，就会产生计算异常。
image
方法二 （动态规划）
def fibo(n):
if n < 1:
return -1
F = [None] * (n+1)
F[1] = 1
F[2] = 2
for i in range(3, n+1):
F[i] = F[i-1] + F[i-2]
return F[n]
image
总结
使用可变对象记录计算过的表达式结果，下次引用的时候可以避免重复计算，再用lru_cache的递归上，倒叙计算的话其实也会产生计算溢出。原因是倒序计算的第一次就是把所有数据重新计算。
对于类似斐波拉契数列的计算算法最好使用动态规划的方法，从基层开始算起，下一层或下几层则引用之前算过的项
