import java.util.HashMap;
class Main {
public static void main(String[] args) {
System.out.println(fibonacci(12));
}
public static int fibonacci(int n) {
HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();
return fibonacciRec(n, cache);
}
private static int fibonacciRec(int n, HashMap<Integer, Integer> cache){
if (n < 1) return 1;
if (cache.containsKey(n))return cache.get(n);
else {
int res = fibonacciRec(n - 1, cache) + fibonacciRec(n - 2, cache);
cache.put(n, res);
return res;
}
}
}
