Learn
Technical Interview Problems: Dynamic Programming
Fibonacci Without Memoization

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:

``f(n) = f(n - 1) + f(n - 2)``

We’ve written a Python function that returns the `n`th Fibonacci number.

Let’s add some print statements so we can see how often we’re repeating work in the current implementation.

### Instructions

1.

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.

2.

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?

3.

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`.

4.

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!