剑指斐波那契数列

斐波那契数列递归解法超时，需要记忆化递归，memo的值需要传入的函数里，因为使用递归方法，如果不传入的话，就会每次初始化，所以在函数里还需再写一个递归函数，也可以写在函数外面。
时间复杂度O(N)没有重复计算。空间复杂度包括额外的数组以及递归栈
递归的时间复杂度为o(2^n) 因为看递调用了多少次，看递归树上的节点
因为害怕出现溢出的问题，所以对结果取模1e9+7
为什么要取模1e9+7
(a+b)%(1e9+7)=a%(1e9+7)+b%(1e9+7)
(ab)%(1e9+7)=a%(1e9+7)b(1e9+7)
1e9+7 加和不会超过int32 乘积不会超过int64
对质数取余会最大程度的避免冲突

Python 3 极大地简化了整数的表示，效果可表述为：整数就只有一种整数（int），没有其它类型的整数（long、int8、int64 之类的）
Numpy 中的整数类型对应于 C 语言的数据类型，每种“整数”有自己的区间，要解决数据溢出问题，需要指定更大的数据类型（dtype）

# -*- coding:utf-8 -*-
class Solution:
    def fib(self,n,memo):

        if n<=1:
            return n
        if memo[n]!=-1:
            return memo[n]
        memo[n]=self.fib(n-1,memo)+self.fib(n-2,memo)
        return memo[n]

    def Fibonacci(self, n):
        # write code here
        memo=[-1]*40
        return self.fib(n,memo)%(1e9+7)

第二种记忆递归，通过类的属性传递memo

# -*- coding:utf-8 -*-
class Solution:

    def __init__(self):
        self.memo=[-1]*46
    def Fibonacci(self, n):
        # write code here


        if n<=1:
            return n
        if self.memo[n]!=-1:
            return self.memo[n]
        self.memo[n]=(self.Fibonacci(n-1)+self.Fibonacci(n-2))%(1e9+7)

        return self.memo[n]

动态规划相对于记忆化递归，只需要保存他的前两位结果就可以，自底向上的方法。注意range里的范围，第一次计算是从fib2开始的。
由于 Python 中整形数字的大小限制取决计算机的内存（可理解为无限大），因此可不考虑大数越界问题。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        fib=0
        a=0
        b=1
        if n<=1:
            return n
        for i in range(2,n+1):
            fib=(a+b)%(1e9+7)
            a,b=b,fib

        return fib

剑指 斐波那契数列

剑指斐波那契数列