LeetCode 斐波那契序列

题目描述

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

思路

最直观的思路是递归，如下

class Solution {
    
    public int fib(int n) {
    
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }
}

但是递归会造成非常多的重复计算，提交会报超时。

动态规划

上面的递归是自顶向下求解（由求解F(n)开始，递归先求解F(n-1)，…一直到F(1)），我们可以在递归的基础上加上记忆化。也可以换个角度，自底向上求解（先求解F(1)，再求解F(2)，最后求解F(n)），于是考虑用动态规划来做，记得加上模运算

class Solution {
    
    int MOD = 1_000_000_000 + 7;
    public int fib(int n) {
    
        if (n <= 1) return n;
        int[] f = new int[n + 1];
        f[1] = 1;
        for (int i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD;
        return f[n];
    }
}

动态规划的时间复杂度是$O(n)$

矩阵快速幂

进阶的做法可以利用矩阵快速幂，将时间复杂度降低为$O(logn)$
利用矩阵乘法可以建立这样一种递推关系：
$$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\times \left[\begin{array}{c}F(n)\\ F(n-1)\end{array}\right]=\left[\begin{array}{c}F(n)+F(n-1)\\ F(n)\end{array}\right]=\left[\begin{array}{c}F(n+1)\\ F(n)\end{array}\right]$$

由此可以推出，如下的关系
$${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n-1}\times \left[\begin{array}{c}F(1)\\ F(0)\end{array}\right]=\left[\begin{array}{c}F(n)\\ F(n-1)\end{array}\right]$$

于是问题就转变成了求一个矩阵的n次幂，而求幂，我们可以用快速幂算法，将时间复杂度降低到$O(logn)$。
只是两个整数的乘法，变成了两个矩阵的乘法。注意矩阵中，我们初始的矩阵应该设为单位矩阵
$$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$
单位矩阵和任意矩阵相乘，都等于被乘的矩阵本身。
这个单位矩阵，就相当于整数1，1与任何数相乘都等于其本身。

关于矩阵乘法，又重新复习了一下大学线性代数的基础知识。有2个矩阵A和B，A有m行，n列，称A是一个 $m\times n$ 的矩阵，B有n行，k列，称B是一个 $n\times k$ 的矩阵。只有当A的列数，等于B的行数时，这两个矩阵才能相乘，相乘得到的结果C，是一个 $m\times k$ 的矩阵。对于结果矩阵C中的第[i,j]个位置的值，其等于矩阵A的第i行，和矩阵B的第j列，每个元素相乘并相加的结果。

class Solution {
    

    int MOD = 1_000_000_000 + 7;

    public int fib(int n) {
    
        if (n <= 1) return n;
        int[][] matrix = {
    {
    1, 1}, {
    1, 0}};
        int[][] res = pow(matrix, n - 1);
        // 由于F(1) = 1, 则最终矩阵的第一行第一列的值, 就是F(n)
        return res[0][0];
    }

	// 快速幂算法
    private int[][] pow(int[][] m, int p) {
    
        int[][] res = {
    {
    1, 0}, {
    0, 1}}; // 单位矩阵, 单位矩阵乘以任何矩阵都等于它本身
        while (p > 0) {
    
            if ((p & 1) == 1) {
    
                res = multi(res, m);
            }
            p >>= 1;
            m = multi(m, m);
        }
        return res;
    }
	
	// 2个矩阵相乘
    private int[][] multi(int[][] matrix1, int[][] matrix2) {
    
        int n1 = matrix1.length, m1 = matrix1[0].length;
        int n2 = matrix2.length, m2 = matrix2[0].length;
        if (m1 != n2) throw new IllegalArgumentException("无法计算矩阵乘法");

        // 矩阵乘法
        int[][] res = new int[n1][m2];
        for (int i = 0; i < n1; i++) {
    
            for (int j = 0; j < m2; j++) {
    
                for (int k = 0; k < m1; k++) {
    
                    res[i][j] = (int) ((res[i][j] + ((long)matrix1[i][k] * matrix2[k][j]) % MOD) % MOD);
                }
            }
        }
        return res;
    }
}