Skip to Content
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 nth 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!

Folder Icon

Sign up to start coding

Already have an account?