斐波那契数列（Python）

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

那么问题来了，当我们要求第n个数是多少时？该如何计算呢？
方法一：

class Solution:
    def fib(self, n: int):  
        # if n == 0:
        #     return 0 
        # elif n == 1:
        #     return 1
        # else:
        #     return self.fib(n-1) + self.fib(n-2)
        #上述算法不适合大数计算，容易超出时间限制
        

方法二：

class Solution:
    def fib(self, n: int): 
		MOD = 10 ** 9 + 7 
		#提问：这里的MOD是啥呀？博主还在寻找中
        if n < 2:
            return n
        p, q, r = 0, 0, 1
        for i in range(2, n + 1):
            p = q
            q = r
            r = (p + q) % MOD
        return r