力扣(LeetCode)之斐波那契数列第n项

题目：

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

示例：

输入：n = 2
输出：1

输入：n = 5
输出：5

方法一：暴力求解（递归）

首先我们可以想到的就是，使用递归来进行求解。就像是树结构一样，一层一层的往下递归，最终递归到最后一层，返回0和1，然后进行求解。

# 暴力求解法
def fun1(num):
    if num == 0: return 0 
    if num == 1: return 1 
    return fun1(num-1) + fun1(num-2)

方法二：去重递归

此算法是针对上述的暴力算法进行改进的一个算法，我们会发现，上述算法的时间复杂度是，所以在该问题的求解过程中会存在大量的重复操作，并且有很多值其实我们是已经算出来了的，那就没有必要再重复求解。那么我们仅需要把求解过的解，进行存储，就可以节省大量的时间。

# 去重递归
def fun2(num):
    arr = [-1] * (num+1)
    return recurse(arr, num)

def recurse(arr, num):
    if num == 0: return 0 
    if num == 1: return 1 
    if arr[num] != -1: return arr[num]

    arr[num] = recurse(arr, num-1) + recurse(arr, num-2)
    return arr[num]

方法三：动态规划（双指针）

这其实是最简单的算法，我们使用循环，进存储两个变量，也就是每一个数的前两个值。我们通过迭代从2一直迭代到n。这样我们的时间复杂度和空间复杂度都很小。但是我们再刷算法提的时候，发现，我们需要对结果进行取模操作。1e9+7 = 1000000007，这是最小的十位数质数，取模之后，就能够将我们的结果约束在整数范围之内了

# 双指针迭代
def fun3(n):
    start = 0
    end = 1 
    if n == 0: return start
    for _ in range(2, n+1):
        sums = start + end 
        start = end 
        end = sums
    return end%1000000007 # 这是为了防止整数溢出