斐波那契数列

import java.io.BufferedInputStream;
import java.util.Scanner;

public class test1 {

    public static long Fibonacci1(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return Fibonacci1(n - 1) + Fibonacci1(n - 2);
    }

    public static long Fibonacci2(int n, long[] dp) {
        if (dp[n] != 0)
            return dp[n];
        if (n == 1 || n == 2) {
            return dp[n] = 1;
        }
        return dp[n] = Fibonacci2(n - 1, dp) + Fibonacci2(n - 2, dp);
    }

    public static long Fibonacci3(int n) {
        long y1 = 1, y2 = 1, y3 = 1;
        for (int i = 3; i <= n; ++i) {
            y3 = y1 + y2;
            y1 = y2;
            y2 = y3;
        }
        return y3;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        long[] dp = new long[n + 1];
        cin.close();
        System.out.println("循环版本斐波那契:" + Fibonacci3(n)); // 循环版本斐波那契，最好
        System.out.println("递归带动态规划的斐波那契:" + Fibonacci2(n, dp)); // 递归带动态规划的斐波那契，次之
        System.out.println("递归基础版本斐波那契:" + Fibonacci1(n)); // 递归基础版本斐波那契，最差，到45以上需要很久才出得来结果
    }
}