// 第 12 周 – 斐波那契数：朴素递归（指数级）、记忆化和迭代（线性）
// 运行：java Fibonacci.java
import java.util.HashMap;

public class Fibonacci {
    static long calls = 0;

    // 朴素递归 – 树形递归，O(2^n) 次调用
    static long fib(int n) {
        calls++;
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    // 记忆化：把已经计算出的值存起来（哈希表！）– O(n)
    static HashMap<Integer, Long> memo = new HashMap<>();

    static long fibMemo(int n) {
        calls++;
        if (n < 2) return n;
        Long cached = memo.get(n);
        if (cached != null) return cached;
        long r = fibMemo(n - 1) + fibMemo(n - 2);
        memo.put(n, r);
        return r;
    }

    // 迭代 – O(n) 时间，O(1) 空间
    static long fibIter(int n) {
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            long t = a + b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(" n   fib(n)        naive calls    memo calls     time (naive)");
        for (int n : new int[] { 5, 10, 20, 30, 40 }) {
            calls = 0;
            long t0 = System.nanoTime();
            long r = fib(n);
            long t = System.nanoTime() - t0;
            long naive = calls;
            calls = 0;
            memo.clear();
            fibMemo(n);
            System.out.printf("%2d %10d %15d %13d %10.1f ms%n", n, r, naive, calls, t / 1e6);
        }
        System.out.println("fibIter(90) = " + fibIter(90));
    }
}