Leetcode Fibonacci sequence

Title Description

Write a function , Input n , Fibonacci, please （Fibonacci） The number of the sequence n term （ namely F(N)）. Fibonacci series is defined as follows ：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), among N > 1.
The Fibonacci series is composed of 0 and 1 Start , The Fibonacci number after that is the sum of the two numbers before .

The answer needs to be modelled 1e9+7（1000000007）, If the initial result of calculation is ：1000000008, Please return 1.

Ideas

The most intuitive idea is recursion , as follows

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

But recursion will cause a lot of double counting , Submission of the report timed out .

Dynamic programming

The recursion above is a top-down solution （ By solving F(n) Start , Solve recursively first F(n-1),… Until F(1)）, We can add Memorization on the basis of recursion . You can also change the angle , Solve from the bottom up （ Solve first F(1), Solve again F(2), Finally, solve F(n)）, So consider using dynamic programming , Remember to add modulo operation

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];
    }
}

The time complexity of dynamic programming is $O(n)$

Matrix fast power

Advanced approach can use matrix fast power , Reduce time complexity to $O(logn)$
Such a recursive relationship can be established by matrix multiplication ：
$$\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]$$

From this we can deduce , The following relationship
$${\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]$$

So the problem turns into finding a matrix n The next power , And exponentiation , We can use fast power algorithm , Reduce time complexity to $O(logn)$.
It's just the multiplication of two integers , It becomes the multiplication of two matrices . Notice in the matrix , Our initial matrix should be set to Unit matrix
$$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$
The identity matrix is multiplied by any matrix , Is equal to the multiplied matrix itself .
This identity matrix , It's equivalent to an integer 1,1 Multiplying by any number equals itself .

About matrix multiplication , I reviewed the basic knowledge of College linear algebra again . Yes 2 Matrix A and B,A Yes m That's ok ,n Column , call A It's a $m\times n$ Matrix ,B Yes n That's ok ,k Column , call B It's a $n\times k$ Matrix . Only when A Columns of , be equal to B The number of lines , These two matrices can be multiplied , The result of multiplication is C, It's a $m\times k$ Matrix . For the result matrix C No [i,j] Value of position , It is equal to matrix A Of the i That's ok , And matrices B Of the j Column , The result of multiplying and adding each element .

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);
        //  because F(1) = 1,  Then the value of the first row and the first column of the final matrix ,  Namely F(n)
        return res[0][0];
    }

	//  Fast power algorithm 
    private int[][] pow(int[][] m, int p) {
    
        int[][] res = {
    {
    1, 0}, {
    0, 1}}; //  Unit matrix ,  The identity matrix multiplied by any matrix is itself 
        while (p > 0) {
    
            if ((p & 1) == 1) {
    
                res = multi(res, m);
            }
            p >>= 1;
            m = multi(m, m);
        }
        return res;
    }
	
	// 2 Matrix multiplication 
    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(" Cannot calculate matrix multiplication ");

        //  Matrix multiplication 
        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;
    }
}