문제 : 피보나치 수열 [ 다이나믹 구현 ]

import java.util.HashMap;

public class Fibonacci {
    public int fibonacci(int n) {
        if(n == 0)
            return 0;
        if(n == 1){
            return 1;
        }
        return fibonacci(n-1) + fibonacci(n-2);

    }

    public int fibonacciFaster(int n) {
        return fibonacciRec(n, new int[n+1]); // 정수배열 선언 시 0으로 초기화 
    }
    private int fibonacciRec(int n, int[] cache){
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        if(cache[n] != 0){
            return cache[n];
        }
        cache[n] = fibonacciRec(n-1, cache) + fibonacciRec(n-2, cache);
        return cache[n];
    }

}