剑指 Offer 10- I. 斐波那契数列

难度简单223

写一个函数，输入 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。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示：

• 0 <= n <= 100

思路:斐波那契数列，一个老生常谈的问题。

1.直接根据公式线性递推:f[i]=f[i-1]+f[i-2]，可以使用滚动数组或双元素优化空间占用。

class Solution {
public:
    int fib(int n) {
        if(!n) return 0;
        const int mod = 1e9 + 7;
        int preF = 0, F = 1, temp;
        for(int i = 2; i <= n; ++ i) {
            temp = F;
            F = (F + preF) % mod;
            preF = temp;
        }
        return F;
    }
};

2.矩阵快速幂。我们可以用矩阵的乘法来表示斐波那契的运算，则有：

 如果我们从F[0]、F[1]递推到第n项，那么公式如下：

 此时我们对矩阵乘法用快速幂去加快前一项的运算即可。

class Solution {
public:

    static const int mod = 1e9 + 7;

    struct martix {
        long long mat[2][2];
        martix operator * (const martix m) {
            martix temp;
            temp.mat[0][0] = (mat[0][0] * m.mat[0][0] % mod + mat[0][1] * m.mat[1][0] % mod) % mod;
            temp.mat[0][1] = (mat[0][0] * m.mat[0][1] % mod + mat[0][1] * m.mat[1][1] % mod) % mod;
            temp.mat[1][0] = (mat[1][0] * m.mat[0][0] % mod + mat[1][1] * m.mat[1][0] % mod) % mod;
            temp.mat[1][1] = (mat[1][0] * m.mat[0][1] % mod + mat[1][1] * m.mat[1][1] % mod) % mod;
            return temp;
        }
    };

    int fib(int n) {
        martix base, m;
        base.mat[0][0] = 1; base.mat[0][1] = 0; base.mat[1][0] = 0; base.mat[1][1] = 1;
        m.mat[0][0] = 1; m.mat[0][1] = 1; m.mat[1][0] = 1; m.mat[1][1] = 0;
        while(n) {
            if(n & 1) {
                base = base * m;
            }
            n >>= 1;
            m = m * m;
        }
        return base.mat[0][1];
    }
};