斐波那契数列题目链接

一、题目描述

JZ7斐波那契数列
题目大意：求斐波那契数列数列的第n项是多少
注意审题：由于题目中函数的返回值是int类型，可知范围一定不会超过int型所能表示的范围

斐波那契数列的定义如下：

二、算法1 (递归）

算法思路

1.总体思路：递归
2.递归边界即F(0)和F(1), 采用自底向上的递归方式, 先递归到边界，然后将结果不断叠加返回即可

代码实现 （C++11）

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};

时间复杂度：O(2^n)
空间复杂度：O(2^n)

三、算法2 （动态规划）

使用动态规划算法,我们可以利用递推式F(x) = F(x - 1) + F(x - 2),将中间结果都记录下来，计算每个F(x)时，我们就用已经计算出的F(x - 1)和F(x - 2)的值来更新它,故我们可以定义数组f, f(i)表示斐波那契数列第i项的值

代码实现 （C++11）

class Solution {
public:
    int Fibonacci(int n) {
        int f[n + 1];
        f[0] = 0;
        f[1] = 1;
        for(int i = 2; i <= n; i++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

空间优化

由于F(x)，实际上我们不需要将0~n的所有状态记录下来,而只需要知道F(x - 1)和F(x - 2)的值即可，因此可以用两个变量来表示，递推即可

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int pre = 0, cur = 1;
        for(int i = 2; i <= n; i++){
            int tmp = pre + cur;
            pre = cur;
            cur = tmp;
        }
        return cur;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

算法3 （矩阵快速幂）

矩阵快速幂擅长解决类似的线性递推问题,因为F(x)是由F(x-1)和F(x-2)递推而来的, 因此我们的结果矩阵可以设置为一个2行一列的矩阵

根据运算, 我们可以求出矩阵A是一个两行两列的系数矩阵

最终可以得到递推方程：

对于,我们可以用快速幂算法在O(logn)的时间复杂度中计算出来

代码实现 (C++11)

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0 || n == 1) return n;
        vector<vector<int>> A{{1, 1},
                              {1, 0}};
        vector<vector<int>> ans = qmi(A, n - 1);
        return ans[0][0];
    }

    // 矩阵快速幂
    vector<vector<int>> qmi(vector<vector<int>>& a, int k){
        // 单位矩阵I
        vector<vector<int>> I{{1, 0},
                              {0, 1}}; 
        while(k){
            if(k & 1) I = mul(I, a);
            a = mul(a, a);
            k >>= 1;
            }
        return I;
    }

    // 实现矩阵乘法
    vector<vector<int>> mul(vector<vector<int>>& a, vector<vector<int>>& b){
        int n = a.size();
        int m = b[0].size();
        int t = b.size();
        vector<vector<int>> c(n, vector<int>(m, 0));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                for(int k = 0; k < t; k++){
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }
};

时间复杂度：O(logn)
空间复杂度：O(1)