斐波那契数列

斐波那契数列
写一个函数，输入  n  ，求斐波那契（Fibonacci）数列的第  n  项。斐波那契数列的定义如下：
F(0)  =  0,    F(1) =  1
F(N)  =  F(N  -  1)  +  F(N  -  2),  其中  N  >  1.
斐波那契数列由  0  和  1  开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模  1e9+7（1000000007），如计算初始结果为：1000000008，请返回  1。

示例  1：
        输入：n  =  2
        输出：1
示例  2：
        输入：n  =  5
        输出：5
提示：
        0  <=  n  <=  100

自我解答：

        这个就和爬楼梯一样，f(n)  =  f(n-1)  +  f(n-2)
        方法一：带备忘自顶向下法

class Solution:
    def fib(self, n: int) -> int:
        self.momo = dict()
        r = self.get_fib(n)
        return r % 1000000007

    def get_fib(self, n: int) -> int:
        if n in self.momo:
            return self.momo[n]
        if n == 0: return 0
        if n == 1: return 1
        r = self.get_fib(n-1) + self.get_fib(n-2)
        self.momo[n] = r
        return r

        方法二：自底向上法  +  滚动数组

class Solution2:
    def fib(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        n1, n2 = 0, 1
        for i in range(2, n + 1):
            n1, n2 = n2, n1 + n2

        return n2 % 1000000007

原题链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof