NC65：斐波那契数列

解法1：递归

斐波那契数列的标准公式为：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
根据公式可以直接写出：

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

时间复杂度：O(2^n)
空间复杂度：O(1)

解法2：动态规划

递归会重复计算大量相同数据，我们用个数组把结果存起来

int Fibonacci(int n) {
    vector<int> dp(n+1, 0);
        dp[1] = 1;
        for (int i=2; i<=n; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
}

解法3：优化存储

优化：发现计算f[5]的时候只用到了f[4]和f[3], 没有用到f[2]...f[0],所以保存f[2]..f[0]是浪费了空间。只需要用3个变量即可

int Fibonacci(int n) {
     if (n == 0 || n == 1) return n;
        int a = 0, b = 1, c;
        for (int i=2; i<=n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
}
时间复杂度：O（n）
空间复杂度：O（1）

继续优化：两个变量

    //非递归的方法 O(N)
    public static int fibonacci2(int n){
        if(n<2){
            return n;
        }
        int a=0,b=1;
        for(int i=2;i<=n;i++){
            b=b+a;//
            a=b-a;//
        }
        return b;
    }

时间复杂度：O（n）
空间复杂度：O（1）

解法4：矩阵乘法

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

矩阵：
[ f(n)   ] = [ 1*f(n-1) + 1*f(n-2) ] = [ 1 1 ] * [ f(n-1) ]
[ f(n-1) ]   [ 1*f(n-1) + 0*f(n-2) ]   [ 1 0 ]   [ f(n-2) ]

 显然：
    [ f(2) ] = [ 1 ]
    [ f(1) ]   [ 1 ]

  假设：
    mul = [ 1 1 ]
          [ 1 0 ]

  那么：
[f(n)  ] = mul * [f(n-1)] = mul*mul*[f(n-2)] = ... = mul^(n-2) * [f(2)]
[f(n-1)]         [f(n-2)]           [f(n-3)]                     [f(1)]

时间复杂度为O(logn)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    //给出一个整数 n，请输出斐波那契数列的第 n 项对 1e9 + 7 取模的值。
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String str = input.readLine();
        String[] inputLine = str.split(" ");
        long m =  Long.parseLong(inputLine[0]);
        System.out.println(fib(m));
    }
    public static long fib(long n) {
        if (n < 1) {
            return 0;
        }
        if (n < 3) {
            return 1;
        }
        long[][] base = {{1, 1}, {1, 0}};
        long[][] res = matrixPower(base, n - 2);
        return (res[0][0] + res[1][0]) % 1000000007;
    }

    public static long[][] matrixPower(long[][] m, long p) {
        long[][] res = new long[m.length][m[0].length];
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        long[][] tmp = m;
        while (p != 0) {
            if ((p & 1) != 0) {
                res = multMatrix(res, tmp);
            }
            tmp = multMatrix(tmp, tmp);
            p >>= 1;
        }
        return res;
    }

    private static long[][] multMatrix(long[][] m1, long[][] m2) {
        long[][] res = new long[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                    res[i][j] = res[i][j] % 1000000007;
                }
            }
        }
        return res;
    }
}