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

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

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.

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

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!