CS173: Intro to Computer Science - Dynamic Programming (3 pts)
Explorer
GitHub
Connect to GitHub to push and pull your project files to a repository.
On the page that opens, create a token with repo scope, copy it, then paste it below.
Paste the personal access token you created on GitHub with repo scope.
Click Refresh to load commit history
Exercise Info
Goals
To improve performance of a recursive algorithm by cacheing values via a Dynamic Program
Instructions
Your job below is to change the fib method so that it checks to see if a particular Fibonacci number has been saved in memory before trying to compute it. If it's already been saved, simply return what's in memory.
In this exercise [1], the main method computes fib(20) and fib(30), and by default, it outputs the following stats:
fib(20) = 10946, counts = 21891
fib(30) = 1346269, counts = 2692537
But once you start using the memory properly, you’ll get these stats instead, which are way more efficient
fib(20) = 10946, counts = 39
fib(30) = 1346269, counts = 21
In fact, now computing fib(30) takes even fewer than the 30 steps we would have done by hand, because we remembered some of the steps we did when computing fib(20) right before that.
Hints
Recall that to see if a key is in a HashMap map, you say map.containsKey(key), which returns true if the key is in the map and false otherwise. So you’d want to check the memory by saying something like fibMem.containsKey(N). You should use the result of this in an if statement
Recall that to retrieve values from the hash map, you use the get(key) method.