Learn
Technical Interview Problems: Dynamic Programming
Fibonacci With Memoization

The Fibonacci sequence is a perfect case to apply dynamic programming. Each Fibonacci number relies on two previous numbers, and those numbers never change. We have overlapping sub-problems!

We’ll store the answers to sub-problems using memoization. Think of it like jotting notes down on a memo.

With each sub-problem, we’ll check if we have a note in our memo. If we do, then we can use that information, otherwise, we’ll need to do a calculation and then store that calculation in our memo pad!

Remember these notes are possible because the answer will always be the same: the `n`th Fibonacci number will never change. Just like the `1 + 1 + 1 + 1` example, we don’t need to recompute the 3rd and 4th Fibonacci number to calculate the 5th Fibonacci number if we already know the 3rd and 4th number.

### Instructions

1.

We’ll store our calculated Fibonacci numbers in a dictionary similar to how we stored the function calls.

Add a second parameter to `fibonacci()` of `memo`. Inside the function, update the recursive calls so `memo` is passed as the second argument.

Update the logging we have outside the function. Invoke `fibonacci()` with `num_in_fibonacci` and `{}` as our initial “memo”.

2.

Each function call now has access to our `memo` dictionary. Alter the function so it checks if we’ve seen this computation already.

Add an `elif` conditional before the recursive function calls and check `memo.get(num)`.

If `memo.get(num)` has a value, we’ve seen the computation and we can return the retrieved value.

3.

We can see the number of function calls hasn’t been reduced!

That’s because we’re never storing anything inside our memo.

Update the final line of the `fibonacci()` function so instead of returning the recursive call it stores the result under `memo[num]`. Now the computation will be available for other function calls.

Once the value has been stored, return `memo[num]`

4.

We’ve successfully applied dynamic programming to the Fibonacci Sequence.

Run the code and see how few function calls are performed compared to our previous solution!