斐波那契问题是算法入门中经常遇到的问题，可以用多种方法求解，下面我将我用到的方法一一列举。现在我们先重述一下问题：

问题重述

已知a₀ = 1，a₁ = 1，a_n = a_n-1 + a_n-2，求a_n的值是多少。

为了考虑整数溢出问题，我们将结果对1000000007取模。

解决方法

一、递归

const int MOD = 1000000007;
int fibonaccia(int n) {
    if(n == 0 || n == 1) {
        retiurn 1;
    }
    else {
        return fibonaccia(n - 1) + fibonaccia(n - 2);
    }
}

递归算法思路和代码均比较容易，时间复杂度为O(n)，在一秒内大概可以算到三十四项。这当然是远远不够的

二、记忆化搜索

const int N = 10000, MOD = 1000000007;
int fibonaccia(int n) {
    if(a[n]) {
        return a[n];
    }
    if(n == 0 || n == 1) {
        return 1;
    }
    a[n] = fibonaccia(n - 1) + fibonaccia(n - 2);
    a[n] %= MOD;
    return a[n];
}

这里开一个大数组来记录结果，如果已经计算过则直接查表，减少了运算次数。对于n个状态，由于每一个状态都要计算1次，因此时间复杂度是O(n)，虽然可以一秒内计算1e7，但是采用递归算法，递归层数较多时会爆栈，因此大概可以计算到1e5的级别

三、动态规划

const int N = 100000000, MOD = 1000000007;
int fibonaccia(int n) {
    a[0] = a[1] = 1;
    for(int i = 2; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2];
        a[i] %= MOD;
    }
    return a[n];
}

这种方法与上一种原理上类似，但是这种方法的瓶颈是数组的内存而不再是栈的层数，因此大概可以计算到1e8，时间复杂度仍为O(n)

四、递归 + 滚动变量

const int N = 100000000, MOD = 1000000007;
int fibonaccia(int n) {
    int a, b, c;
    a = 1;
    b = 1;
    while(n --) {
        c = (a + b) % MOD;
        a = b;
        b = c;
    }
    return a;
}

例如这道题：斐波那契数列

虽然时间复杂度仍然是O(n)，但是空间复杂度变成了O(1)。

五、矩阵快速幂

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
​
using namespace std;
​
typedef long long LL;
​
const int MOD = 1000000007;
​
void mul(int a[][2], int b[][2], int c[][2]) {
    int temp[][2] = {{0, 0}, {0, 0}};
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            for(int k = 0; k < 2; k++) {
                LL x = temp[i][j] + (LL)a[i][k] * b[k][j];
                temp[i][j] %= MOD;
            }
        }
    }
    memcpy(c, temp, sizeof temp);
}
​
int fibonaccia(LL n) {
    if(n == 0) {
        return 1;
    }
    
    int x[2] = {1, 1};
    int res[][2] = {{1, 0}, {0, 1}};
    int t[][2] = {{1, 1}, {1, 0}};
    
    LL k = n - 1;
    while(k) {
        if(k & 1) {
            mul(res, t, res);
        }
        mul(t, t, t);
        k >>= 1;
    }
    
    int c[2] = {0, 0};
    for(int i = 0; i < 2; i++) {
        LL r = c[i] + (LL)x[j] * res[j][i];
        c[i] %= MOD;
    }
    return c[0];
    
}
​
int main()
{
    LL n;
    
    cin >> n;
    cout << fibonaccia(n) << "\n";
    
    return 0;
}
​

矩阵快速幂通过矩阵的方式，可以找到第n项与第1项之间的递推关系，矩阵的n次方可以采用快速幂的方法，由于快速幂的时间复杂度是O(n)，因此该方法的时间复杂度是O(n)。

六、通项公式

由于F(n) = F(n - 1) + F(n - 2)，

我们可以写出特征方程：x^2 = x + 1

求得x_1 = \frac{1 + \sqrt{5}}{2}

设通解为F(n) = c_1x_1^n + c_2x_2^n，

带入初始条件F(0) = 0，F(1) = 1，

得c_1 = \frac{1}{\sqrt{5}}，c_2 = -\frac{1}{\sqrt{5}}

因此斐波那契数列的通项公式为：

F(n) = \frac{1}{\sqrt{5}}[(\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n]

那么在得到该通项公式后，我们就可以在O(1)的时间复杂度内求解第n项。

感悟

一个小小的问题背后其实蕴含着算法功底的成长：递归的算法是我们最一开始接触的，是实现起来最简单、但是同时时间复杂度也是最高的；其次是记忆化搜索和动态规划，思路上主要是为了减少递归的计算量，使得每一个状态只进行一次计算，因此能够降低时间复杂度，将时间复杂度控制在O(n)；然后，相同的思路下，我们可以优化空间，只是用3个变量就可以计算第n项的斐波那契数列值；最后，我们借用快速幂运算快的特性，将时间复杂度控制在O(logn)级别。另外补充了一个通项公式的做法，这种方法有很大的局限性：随便换一道题就不能这样做了，但我觉得经典的斐波那契数列通项公式值得牢记