剑指offer - 斐波那契数列(Java实现)

题目链接：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&&tqId=11160&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路一：递归，如图递归的来计算第 n 个斐波那契数。
斐波那契递归

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

思路二：记忆化数组，从递归方法中的图来看，在递归的过程中，我们需要进行大量的重复计算，这样就大大降低了程序的执行效率，我们可以使用一个记忆化数组来保存已经计算过的数组，这个就可以降低程序的时间复杂度。

public class Solution {
    static int[] F = new int[40];
    public int Fibonacci(int n) {
        for(int i = 0; i < 40; ++ i) F[i] = 0;
        if(n == 0) return 0;
        if(n == 1) return 1;
        return f(n);
    }
    public static int f(int n) {
        if(F[n] != 0) return F[n];
        if(n == 0) return 0;
        if(n == 1) return 1;
        return F[n] = f(n - 1) + f(n - 2);
    }
}

思路三：递推，f[n] = f[n - 1] + f[n - 2];

public class Solution {
    static int[] F = new int[40];
    public int Fibonacci(int n) {
        F[0] = 0; F[1] = 1;
        for(int i = 2; i <= n; ++ i) {
            F[i] = F[i - 1] + F[i - 2];
        }
        return F[n];
    }
}

思路四：矩阵快速幂。 $F_{n} = F_{n - 1} + F_{n - 2}$ ，我们令:
$X_{n-1} = \begin{bmatrix}F_{n-1}\\ F_{n-2} \end{bmatrix}$ $X_{n} = \begin{bmatrix} F_{n}\\ F_{n-1} \end{bmatrix}$
那么我们需要找到的矩阵 A 就满足：
$A \cdot X_{n-1} = X_{n}$
又因为：
$\begin{cases} F_{n} = F_{n-1} + F_{n-2}\\ F_{n-1} = F_{n-1} + 0 \cdot F_{n-2} \end{cases}$
所以：
$A = \begin{bmatrix} 1,1\\ 0,0 \end{bmatrix}$
即：
$\begin{bmatrix} 1,1\\ 0,0 \end{bmatrix}$ $\cdot$ $\begin{bmatrix}F_{n-1}\\ F_{n-2} \end{bmatrix}$ $= \begin{bmatrix} F_{n}\\ F_{n-1} \end{bmatrix}$
综上所述：
$\begin{bmatrix} F_{n}\\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1,1\\ 0,0 \end{bmatrix} \cdot \begin{bmatrix}F_{n-1}\\ F_{n-2} \end{bmatrix} = \begin{bmatrix} 1,1\\ 0,0 \end{bmatrix}^{2} \cdot \begin{bmatrix}F_{n-2}\\ F_{n-3} \end{bmatrix} \cdot \cdot \cdot \cdot =\begin{bmatrix} 1,1\\ 0,0 \end{bmatrix}^{n-1} \cdot \begin{bmatrix}F_{1}\\ F_{0} \end{bmatrix}$

我们用矩阵快速幂求出 $\begin{bmatrix} 1,1\\ 0,0 \end{bmatrix}^{n-1}$ 后，结果矩阵的第一行与上面公式中最后的 $\begin{bmatrix}F_{1}\\ F_{0} \end{bmatrix}$ 做矩阵乘法即是最终结果。

快速幂：https://blog.nowcoder.net/n/f93bed69e38f474a839cb5105d0babc2

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int[][] a = new int[2][2];
        init(a);
        int[][] ans = quickPow(a, n - 1);
        return ans[0][0];
    }
    static int[][] init(int[][] a) {
        a[0][0] = 1; a[0][1] = 1;
        a[1][0] = 1; a[1][1] = 0;
        return a;
    }
    static int[][] quickPow(int[][] a, int b) {
        int[][] ans = new int[2][2], res = new int[2][2];
        init(ans); init(res);
        ans[0][1] = 0; ans[1][0] = 0; ans[1][1] = 1;
        while(b > 0) {
            if(b % 2 == 1) ans = mul(ans, res);
            res = mul(res, res);
            b >>= 1;
        }
        return ans;
    }

    static int[][] mul(int[][] a, int[][] b) {
        int[][] z = new int[2][2];
        for(int i = 0; i < 2; ++ i) {
            for(int j = 0; j < 2; ++ j) {
                z[i][j] = 0;
                for(int k = 0; k < 2; ++ k) {
                    z[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return z;
    }
}