Problem: Fibonacci with Memoization

The chapter fixed the exponential running time of recursive fib by dropping the recursion and building the sequence up from the bottom. An aside mentioned there is another way: keep the recursion and have it store its results in a cache. This problem asks you to write that version.

The signature stays the same as the chapter’s:

public static int fib(int n) {
  // Your implementation goes here
}

Assume n >= 0, as the chapter does, and that the answer fits in an int.