题目链接：
https://leetcode-cn.com/problems/fibonacci-number/
斐波那契数，通常用F(n)表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你 n ，请计算 F(n) 。
示例 1：
输入：2 输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
纯递归
递归有两个基本要素：基例以及递归关系式。
- 基例：F(0) = 0,F(1) = 1,即递归结束的地方
- 递归关系式：F(n) = F(n-1) + F(n- 2)
def fib(n):
#base case
if n <= 1:
return n
elif n >= 2:
return fib(n-1) + fib(n-2)
然后根据python语法特性，可以缩写为一句话
def fib(n):
return fib(n-1) + fib(n-2) if n >= 1 else n
优化
F(20) = F(19)+F(18)
F(19) = F(18)+F(17)
然后我们发现 F(18) 重复，即冗余结构。这样的运算时间会很大，
节点数 * 每个子问题所需要的时间 = 时间复杂度
显而易见，这种情况下为O(2^N)
纯递归的缺点就在于存在过多冗余结构。
递归加记忆
将指数级时间将为多项式级时间。
我们可以将已经出现计算好的存在一个备忘录里面，这样我们下一次计算之前，先去查一遍表就行，不需要再重新计算。
memo = {}
def fib(n):
#查表
if n in memo:
return memo[n]
#base case:
elif n <= 1:
return n
else:
ans = fib(n-1) + fib(n-2)
memo[n] = ans
return memo[n]
解释
当然，上述的备忘录既可以采用数组，同时也可以用哈希表。
另外，如果追求完美一点，可以将基例存储到备忘录里面，这样可以减少一定程度的空间复杂度。
memo = {0:0,1:1}
这里介绍的是由上而下的方法，当然也可以是由下而上的。虽然比纯递归好，但是时间复杂度依然很高，leetcode上为1500-1600ms左右。
bottem-up-solution
def fib(n):
memo = {0:0,1:1}
for i in range(2,n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
解释
for循环的左边是因为备忘录里面已经有键0，1了，所以从2开始。然后我们最后要计算的是memo[n],i = n 所以要为n+1
优化
这个的时间复杂度会大大降低，两者看似都是查表，但是由下而上的这种不会重新迭代函数，只会不断计算表。leetcode数据为36ms
算法方面的优化到此为止，但是关于空间复杂度可以更优化一点，
import sys
h = {0:0,1:1}
l = [0,1]
print(sys.getsizeof(h))
print(sys.getsizeof(l))
#232
#72
字典的空间复杂度远大于列表，所以可以更优化一点。单方面来讲，复杂度跟元素大小无关。跟元素个数有关。
def fib(n):
if n == 0:
return 0
memo[1 for i in range(n+1)]
memo[0],memo[1] = 0,1
for i in range(2,n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
解释
关于第一行生成len = n+1的原因，因为最后返回索引为n,而索引从0开始
而且除了列表生成器的表达，还可以 memo = [1] * (n+1)
之所以提取生成长度为n+1的列表，是为了防止列表索引不够，进行有序的替换。
因为是替换的，所以初始化列表的值是任取的，只要保证基例正确就行。
要小心的是，如果输入0没有开头的if语句是会报错的，原因在于生成了长度为1的列表，却有memo[1] = 1这种操作，然而，列表并不像字典一样可以创建，则导致长度不够用报错
关于for 循环
for i in range(2,1)
for i in range(2,2)
#两者均不会报错且都不执行
经验之谈
还有就是力扣的很多时候判别的不准，大家只要往死里优化，看看几个最优解就行。不必苛求100%，大家可以复制几个100%，有些是运气100%，到你这就不是100%
拓展
滚动变量
def fib(n):
if n == 0:
return 0
for i in range(n):
a,b = b,a+b
return a
这种方法显然不是最优解，但是值得一说的是，按照一些书中python的代码规范。这种结构可读性不好，建议少用。
还有一个更流氓一点的解法：
面对答案编程
class Solution:
def fib(self, n: int) -> int:
a = [0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
return a[n]
细心的同学注意到n的范围为[0,30],所以生成一个长度为31的列表就行。