Part 4: Fibonacci on Steroids The Fibonacci we wrote in Part 1 was very very slow. Can we make this faster? Of course! Let's see how. Everytime we called the subfunction (with n-1 and n-2), we are solving the Fibonacci problem for a smaller input. However, can you notice anything interesting about what smaller inputs we might see? A huge problem with a purely recursive implementation to this problem is that we end up solving the same problem for the same numbers over and over again. Take a look: 1(6) f(4) f(3) f(4) f(3) 1(2) 1(2) f(2) f(1)1 f(2) f(1)1 f(1)1 t(0)0 f(1)1 f(O) = O f(3) f(2) f(1)1 f(0)0 Look at how many numbers we recompute the FULL answer for! In order to optimize this horrifically slow algorithm (O(2'n) level of slow), we can memoize (or remember the answer to) the solutions to inputs. Write the code for this function in Java but add memoization to eliminate duplicate work. (Hint: you can use an array or a hash map data structure to accomplish this. If it makes it easier, you can store this as a global variable)