Memoization in Dynamic Programming
What is Dynamic Programming?
Dynamic programming is a technique that allows us to solve a class of problems that have overlapping subproblems and optimal substructure. Let’s dive deeper into these concepts.
A problem has an optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its subproblems. For Fibonacci numbers, as we know, fib(n) = fib(n — 1) + fib(n — 2).
This clearly shows that a problem of size n has been reduced to subproblems of sizes n-1 and n-2. Therefore, Fibonacci numbers have optimal substructure property.
A recursive algorithm that has to compute the same problems multiple times has overlapping subproblems. Let’s take a look at the recursive Fibonacci solution and see how this algorithm works.
So here’s our naive approach to solving the Fibonacci problem. We can see that our function returns the correct value, but what happens if we’re trying to find an answer for a greater position in a sequence?
As we can see, using this solution for greater values very quickly becomes impractical.
But why is it so slow? To understand this, let’s break down our earlier example of fib(7) and visualize our recursive calls in the form of a tree.
Wow! Look at this, even to compute such a small position 7, we had to call our function 25 times!
Given return fib(n — 1) + fib(n — 2) we know that for each function call, it’s going to call itself twice, and each one of those calls will call itself twice as well, and so on.
This gives us an exponential time complexity O(2^n).
But let’s examine what exactly is computed in our tree.
We can notice that we have a lot of subtrees that compute the same value. For fib(7) we compute fib(3) 5 times, fib(4) 3 times, and fib(5) 2 times. This is exactly what it means to have overlapping subproblems.
We’re solving the same problems over and over again and it is very inefficient. There must be a way to optimize this.
If we have to solve the same problem over and over again, we may cache function return values, and simply retrieve them from our cache if we encounter a problem that we’ve solved before.
We can facilitate this by using a memo object that will be populated with key-value pairs of n : fib(n) and passed down to our recursive calls.
The only difference between this solution and a previous solution is that when the function is called for the first time, we pass an empty memo object that is populated with return values of the function and passed down to other recursive calls.
If we see that n was previously saved in a memo, we can return the cached value from our memo in constant time and avoid subsequent recursive calls on a branch.
Let’s see what our recursive tree looks like now.
We can see that we greatly reduced the number of recursive calls. From 25 function calls without memoization to 11 with memoization.
Also, even if we’re going to pass a greater value as an input and use memoization, our recursive tree will still resemble this linear chain-like structure.
Our memoization strategy greatly improved the time complexity of the solution. From exponential O(2^n) to linear O(n).
Let’s take one of the examples that we used previously and see how our function is performing now, with memoization implemented.
Before memoization, we were unable to compute fib(100) in a reasonable time at all, and our console appeared to be frozen. But now we’re able to compute it roughly in 1 second.
Dynamic Programming is a very nice way to solve optimization problems, that allows us to use recursion effectively and avoid computing the same problems multiple times.
DP can sometimes be hard to grasp, so feel free to go over this blog again.
I encourage using a whiteboard to draw out your recursive trees with and without memoization to develop a better understanding of DP.