Storing answers to sub-problems is an essential aspect of dynamic programming. Let’s explore why this is the case.
The Fibonacci Sequence is a series of numbers where the next number equals the sum of the previous two, starting with 0 and 1.
Here’s a list of the first 10 Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21. The zeroth Fibonacci number is 0.
We can express this sequence as a function:
We’ve written a Python function that returns the nth Fibonacci number.
Let’s add some print statements so we can see how often we’re repeating work in the current implementation.
Instructions
We need a way to store our function calls.
Above the fibonacci() function, declare arguments_count as an empty dictionary.
arguments_count will hold the argument as a key and the number of times we called fibonacci() with that argument as the value.
We need to fill our dictionary so we can log the results.
Inside the first line of the fibonacci() function, declare the variable count. Set count to be the value located in arguments_count under the key num.
Sometimes that key won’t exist because the argument hasn’t been seen before.
Use 0 as a default. What dictionary method would be useful here?
With a sensible default in place, reassign count to be one more than it was previously to mark this function call.
After incrementing, store the updated value back in arguments_count with the same key of num.
We’ve successfully completed our logging. Run the function.
See how often arguments are repeated? Change num_in_fibonacci to different numbers.
The bigger the number, the more repetitions!