斐波那契数列

题目描述：
求斐波那契数列的第 n 项，n<=39。
f(n) = 0 , n = 0;
f(n) = 1 , n = 1;
f(n) = f(n-1)+f(n-2) , n>1;

f(1)+f(0) = 1+0 = 1 ; n = 2;
f(2)+f(1) = 1+1 = 2 ; n = 3;
f(3)+f(2) = 2+1 = 3 ; n = 4;

解题思路：
如果使用递归求解，会重复计算一些子问题。例如，计算 f(10) 需要计算 f(9) 和 f(8)，计算 f(9) 需要计算 f(8) 和 f(7)，可以看到 f(8) 被重复计算了。
递归方法是将一个问题划分成多个子问题求解，动态规划也是如此。但是动态规划会把子问题的解缓存起来，避免重复求解子问题。

public class SortClass {

    public static void main(String[] args){
        int num = fibonacci(3);
        System.out.println(num);
        
        // 运行结果：
        // 2
    }

    public static int fibonacci(int n){
        if (n<=1){
            return n;
        }
        // 值默认为 0
        int[] fib = new int[n+1];
        fib[1]=1;
        // 假设 n =  3,会循环两次。
        // fib[2]=fib[1]+fib[0]; 1+0
        // fib[3]=fib[2]+fib[1]; 1+1
        for (int i = 2; i <= n ; i++) {
            fib[i]=fib[i-1]+fib[i-2];
        }
        return fib[n];
    }
}

考虑到第 i 项只与第 i-1 和第 i-2项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。

public class SortClass {

    public static void main(String[] args){
        int num = fibonacci(6);
        System.out.println(num);

        // 运行结果：
        // 8
    }

    private static int fibonacci(int n){
        if (n<=1){
            return n;
        }
        int pre2=0,pre1=1;
        int fib=0;
        for (int i = 2; i <=n ; i++) {
            fib=pre2+pre1;
            pre2 = pre1;
            pre1=fib;
        }
        return fib;
    }
}

由于待求解的 n 小于 40，因此可以将前 40 项的结果先进行计算，之后就能以 O(1) 时间复杂度得到第 n 项的值了。

public class SortClass {

    private static int[] fib = new int[40];

    public static void main(String[] args){
       fib[1] = 1;
        int length = fib.length;
        for (int i =2;i<length;i++){
            fib[i] = fib[i-1]+fib[i-2];
        }

        System.out.println(Arrays.toString(fib));

        // 运行结果：
        // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 
        // 144, 233, 377, 610, 987, 1597, 2584, 4181,
        // 6765, 10946, 17711, 28657, 46368, 75025,
        // 121393, 196418, 317811, 514229, 832040, 
        // 1346269, 2178309, 3524578, 5702887, 9227465,
        // 14930352, 24157817, 39088169, 63245986]
    }

    private static int fibonacci(int n){
      return fib[n];
    }
}