斐波那契数列 Fibonacci
斐波那契数列是这样的数列：
0、1、1、2、3、5, 8、13、21、34 ……
下一项是上两项的和。
2 是上两项的和（1+1）
3 是上两项的和（1+2）、
5 是（2+3）、
依此类推！
更多有意思的介绍可以见参考链接；
算法
1. 直接递归
初步想法就是采用递归的方式去实现fib(n) = fib(n-1) + fib(n-2)
def fib(n):if n == 1:return 0if n == 2:return 1return fib(n-1) + fib(n-2)
以n=6为例，可以看到fib(6)分解为fib(5)、fib(4)，fib(5)分解为fib(4)、fib(3),fib(4)分解为fib(3)、fib(2), 等等
可以看到这个过程中会有重复计算的过程；相当于每个fib(k)都要被计算2次， n个数字，则需要计算2^n次，所以时间复杂度为O(2^n); 由于采用递归的方式，需要用栈保存每次递归的结果，然后一直到头后再反向得到结果，需要用O(n)的空间去存储fib(n)、fib(n-1)..., fib(1)， 所以空间复杂度为O(n);
2. 递归+hashmap
那么借助于**空间换时间**的思想，使用hashmap去保存每次计算到的fib(k),需要用到fib(k)时候，直接去hashmap中查就行，不用重复计算；
def fib(n, memorize={1:0, 2: 1}):if n in memorize:return memorize[n]memorize[n] = fib(n-1, memorize) + fib(n-2, memorize)return memorize[n]
时间复杂度为O(n), 空间复杂度为O(n)
3. 递归+两变量
相较于上面的每个fib(i)都保存，可以只保留
从头开始算，可以只保留最近的两个元素的值就可以的
def fib(n):lastTwo = [0, 1]counter = 3while counter <= n:nexFib = lastTwo[0] + lastTwo[1]lastTwo[0] = lastTwo[1]lastTwo[1] = nexFibcounter += 1return lastTwo[1] if n > 1 else lastTwo[0]
时间复杂度为O(n), 空间复杂度为O(1)
