import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) {
CachedFib fib = new CachedFib();
String fmt = "fib(%d) = %d%n";
for (int i = 0; i <= 10; ++i) {
System.out.printf(fmt, i, fib.fibonacci(i));
}
System.out.printf(fmt, 100, fib.fibonacci(100));
}
}
class CachedFib {
private List<BigInteger> cache = new ArrayList<>();
public CachedFib() {
cache.add(new BigInteger("0"));
cache.add(new BigInteger("1"));
}
public BigInteger fibonacci(int n) {
BigInteger result;
if (n < cache.size()) {
result = cache.get(n);
} else {
result = fibonacci(n - 1).add( fibonacci(n - 2) );
cache.add(result);
}
return result;
}
}
