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
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:
f(n) = f(n - 1) + f(n - 2)
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.
We need a way to store our function calls.
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 to be the value located in
arguments_count under the key
Sometimes that key won’t exist because the argument hasn’t been seen before.
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
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!