Java 四种方法实现斐波那契数列

public class Main {
    
    /* 0 1 2 3 4 5
     * 0 1 1 2 3 5 8 13 ...
     * *
     */
    public static int fib1(int n) {
        // 方法一:递归法
        if (n <= 1) return n;
        return fib1(n - 1) + fib1(n - 2);
    }
    
    public static int fib2(int n) {
        // 方法二: 记忆化搜索
        int[] memo = new int[n+1];  // 自定义数组的默认值都为0
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        // 当数组的值为0时，才进行迭代
        if (memo[n] == 0) {
            memo[n] = fib1(n-1) + fib1(n-2);
        }
        
        return memo[n];
    }
    
    
    public static int fib3(int n) {
        // 方法三: 数组自下而上的思考方式
        int[] memo = new int[n+1];
        memo[0] = 0;
        memo[1] = 1;
        for (int i = 2; i <= n; i++) {
            memo[i] = memo[i - 2] + memo[i - 1];
        }
        return memo[n];
    
    }
    
    public static int fib4(int n) {
        // 方法四:自下而上法
        if (n <= 1) return n;
        
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }

    public static void main(String[] args) {
        System.out.println("四种实现斐波那契数列的方法");
        
        System.out.println(fib1(5));
        System.out.println(fib2(5));
        System.out.println(fib3(5));
        System.out.println(fib4(5));
    }

}