斐波那契数 （通常用 F(n) 表示）形成的序列称为斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

普通递归

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

public int fib(int n) {    if (n < 2) {        return n;    }    int pre = 0;    int suf = 1;    for (int i = 2; i <= n; i++) {        int tmp = suf;        suf += pre;        pre = tmp;    }    return suf;}

public int fib(int n, int pre, int result) {    if (n == 1) {        return result;    } else {        return fib(--n, result, result + pre);    }}

推广公式：

// O(logN)public int fib(int n) {    if (n < 2) {        return n;    }    // [ 1, 1 ]    // [ 1, 0 ]    int[][] base = {         { 1, 1 },         { 1, 0 }     };    int[][] res = matrixPower(base, n - 2);    return res[0][0] + res[1][0];}public int[][] matrixPower(int[][] m, int p) {    int[][] res = new int[m.length][m[0].length];    for (int i = 0; i < res.length; i++) {        res[i][i] = 1;    }    // res = 矩阵中的1    int[][] t = m; // 矩阵1次方    for (; p != 0; p >>= 1) {        if ((p & 1) != 0) {            res = product(res, t);        }        t = product(t, t);    }    return res;}// 计算两个矩阵相乘的结果public static int[][] product(int[][] a, int[][] b) {    int aRowNum = a.length;    int bColNum = b[0].length;    int aColNum = a[0].length; // a的列数同时也是b的行数    int[][] ans = new int[aRowNum][bColNum];    for(int i = 0 ; i < aRowNum; i++) {        for(int j = 0 ; j < bColNum; j++) {            for(int k = 0; k < aColNum; k++) {                ans[i][j] += a[i][k] * b[k][j];            }        }    }    return ans;}