斐波拉契数列

题目：

写一个函数，输入n，求斐波拉契（Finonacci）数列的第n项。斐波拉契数列的定义如下：

$$
f(n)=\begin{cases} 0 \quad n=0 \ 1 \quad n=1 \ f(n-1) + f(n-2) \quad n>1 \end{cases}
$$

方案一：使用递归

public static long recursiveFibonacci(int n) {
    if (n <= 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
}

缺点： 要求f(10)，需要先求得f(9) 和 f(8)；要求f(9)，需要先求的f(8) 和 f(7)，依此类推，每求一个数，就必须先求得它前面两个数，有很多数都是重复计算，导致时间复杂度变成 O(2^n)。如果 n 的值过大，会计算缓慢，甚至导致内存溢出。

方案二：O(n) 解法

public static long getFibonacci(int n) {
    int[] result = {0, 1};

    if (n < 2) {
        return result[n];
    }

    long fibonacciOne = 0;
    long fibonacciTwo = 1;
    long fibonacciN = 0;

    for (int i = 2; i <= n; i++) {
        // f(2) = f(0) + f(1)
        // f(3) = f(1) + f(2)
        // ... 不需要使用递归
        fibonacciN = fibonacciOne + fibonacciTwo;
        fibonacciOne = fibonacciTwo;
        fibonacciTwo = fibonacciN;
    }

    return fibonacciN;
}

使用一个循环计算出第n个数的值。

上面 方案一 中，从高到低递归，会有很多重复计算；所以这里采用了从低到高的计算方式，减少了计算次数，大大提高了效率，是一种比较实用的方式。

使用数组递推的方式

public static long arrayFibonacci(int n) {
    int[] arr = new int[n+1];
    arr[0] = 0;
    arr[1] = 1;

    if (n == 0) {
        return arr[0];
    }

    if (n == 1) {
        return arr[1];
    }

    for (int i = 2; i < n+1; i++) {
        arr[i] = arr[i - 2] + arr[i - 1];
    }

    return arr[n];
}

方案三：O(logn)的解法

使用矩阵：
\left[\matrix{f(n) & f(n-1)\ f(n-1) & f(n-2)} \right] = \left[\matrix{1 & 1\ 1 & 0} \right]^{n-1}

$$
\begin{bmatrix} f(n) & f(n-1) \ f(n-1) & f(n-2) \end{bmatrix} = \begin{bmatrix} 1 & 1\ 1 & 0 \end{bmatrix}^{n-1}
$$

上面公式中求得右边部分的值，即可求出 斐波拉契数列第n项。所以问题变为如何求矩阵的乘方，根据乘方的性质，有如下公式成立：
$$
x f(n)=\begin{cases} a^{n/2}.a^{n/2} \quad n为偶数 \ a^{n-1/2}.a^{n-1/2}.a \quad n为奇数 \end{cases}
$$
从上面公式中我们可以看出，要求n次方，需要先求得 n/2 次方，然后再把结果平方以下即可。这里可以使用 递归

代码： 实现比较复杂

/**
  * 采用矩阵的解法
  * 时间复杂度为O(logN)
  * @param n
  * @return
  */
public static int matrix(int n){
    if (n == 0){
        return 0;
    }
    int[][] fbnq = fbnq(n);
    return fbnq[0][1];
}

/*矩阵处理核心代码*/
private static final int[][] UNIT = {{1,1}, {1,0}};
private static int[][] fbnq(int n){
    if (n == 1){
        return UNIT;
    }
    if (n % 2 == 0){
        int[][] matrix = fbnq(n / 2);
        return matrixMultiply(matrix, matrix);
    }else {
        int[][] matrix = fbnq((n-1) / 2);
        return matrixMultiply(UNIT, matrixMultiply(matrix, matrix));
    }
}

/*矩阵乘法*/
private static int[][] matrixMultiply(int[][] a, int[][] b){
    int rows = a.length;
    int cols = b[0].length;
    int[][] matrix = new int[rows][cols];
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < b[0].length; j++) {
            for (int k = 0; k < a[i].length; k++) {
                matrix[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return matrix;
}

扩展：青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法。

分析：

​ 如果只有1级台阶，只有一种跳法；如果有2级台阶，就有两种跳法：分两次跳，每次1级、一次跳2级；我们把n级台阶时的跳法看成 f(n) 函数，当 n>=2时，有两种选择：一是第一次跳1级，此时跳法等于后面 n-1 级的跳法数目，即为 f(n-1) ；二是第一次跳2级，此时跳法数等于后面 n-2 级的跳法数目，即为 n-2。因此总数 ：

f(n) = f(n-1) + f(n-2)。