你真的懂Fibonacci sequence吗？

斐波那契数列：
斐波那契数列递推关系式如下：

题目：求解斐波那契数列第n项？**

1. 递归方法

def Fibonacci(n):
    if n == 0 or n == 1:
        return n
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

通过画出递归树，上述代码存在大量重复的操作。
例如，计算。
可以看到重复计算了。

2. 递归方法优化

如何减少重复计算呢？这里跟动态规划中剪枝的思想类似，构建一个DPTable，存储已计算过的项，达到利用空间换时间。

def Fibonacci(n):
    if n == 0 or n == 1:
        return n
    dp = [0] * (n+1) # 构造有n个元素的列表，存储已计算过的项
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[i]

时间复杂度：，空间复杂度。

3. 分治策略

斐波那契数列是二阶递推数列，存在一个的矩阵，使得：

求解可得：

接下来就是求解。
指数的幂次方直接计算需要计算次乘法，通过二分法来求解，只需要计算。

def metric_product(x, base):
            a = x[0][0]*base[0][0] + x[0][1]*base[1][0]
            b = x[0][0]*base[0][1] + x[0][1]*base[1][1]
            c = x[1][0]*base[0][0] + x[1][1]*base[1][0]
            d = x[1][0]*base[0][1] + x[1][1]*base[1][1]
            return [[a, b], [c, d]]
def fib(self, n: int) -> int:
        if n == 0:
            return 0
        def metric(n):
            base = [[1, 1], [1, 0]]
            # 求 pow(base, n)
            if n == 1:
                return base
            elif n % 2 == 0:
                half = metric(n//2)
                return metric_product(half, half)
            else:
                half = metric(n//2)
                return metric_product(metric_product(half, half), base)
        ans = metric(n)
        f_n = ans[0][1]
        return f_n

4. 动态规划

为了减少空间复杂度

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

时间复杂度, 空间复杂度。

5. 求第n项关于10007的余数

利用余数的性质3，简化最后直接求出f(n)再算余数的复杂，同时也保证了数值不溢出。虽然python支持大数，这个方法也适用于其他语言。

def fab(n):
    a, b = 1, 1
    for _ in range(2, n):
        b, a = (a+b) % 10007, b % 10007
    return b
n = int(input())
ans = fab(n)
print(ans % 10007)