In this solution, we are creating a cache or an array to store our solutions. If there is an already computed solution in the cache, then we would just return it else we compute the result and add it to the cache.

For example, if we are calculating fib(4), the subproblems are fib(3) and fib(2). These solutions are then stored in the cache. Then, when we are calculating fib(3), our program checks to see if fib(2) and fib(1) were already stored inside the cache. We would continue until we hit our base case when our value n is less than 2.

Our new solution only has to compute each value once, so it runs in O(n) time complexity and O(n) space complexity because of the cache.