Dynamic Programming Through Memoization

Luckily, we do have options, and that is through something called dynamic programming. Dynamic programming is the process of optimizing recursive problems that have overlapping subproblems.

(Don’t pay too much attention to the word dynamic. There’s some debate about how the term came about, and there’s nothing obviously dynamic about the techniques I’m about to demonstrate.)

Optimizing an algorithm with dynamic programming is typically accomplished with one of two techniques.

The first technique is something called memoization. And no, that’s not a typo. Pronounced meh-moe-ih-ZAY-shun, memoization is a simple, but brilliant, technique for reducing recursive calls in cases of overlapping subproblems.

Essentially, memoization reduces recursive calls by remembering previously computed functions. (In this respect, memoization really is like its similar-sounding word memorization.)

In our Fibonacci example, the first time fib(3) is called, the function does its computation and returns the number 2. However, before moving on, the function stores this result inside a hash table. The hash table will look something like this:

This indicates that the result of fib(3) is the number 2.

Similarly, our code will memoize the results of all new computations it encounters. After encountering fib(4), fib(5), and fib(6), for example, our hash table will look like this:

Now that we have this hash table, we can use it to prevent future recursive calls. Here’s the way this works:

Without memoization, fib(4) would normally call fib(3) and fib(2), which in turn make their own recursive calls. Now that we have this hash table, we can approach things differently. Instead of fib(4) just blithely calling fib(3), for example, it first checks the hash table to see if the result of fib(3) has already been computed. Only if the 3 key is not in the hash table does the function proceed to call fib(3).

Memoization goes for the jugular of overlapping subproblems. The whole issue with overlapping subproblems is that we end up computing the same recursive calls over and over again. With memoization, though, each time we make a new calculation, we store it in the hash table for future use. This way, we only make a calculation if it hasn’t ever been made before.

Okay, this all sounds good, but there’s one glaring problem. How does each recursive function get access to this hash table?

The answer is this: we pass the hash table as a second parameter to the function.

Because the hash table is a specific object in memory, we’re able to pass it from one recursive call to the next, even though we’re modifying it as we go. This is true even as we unwind the call stack. Even though the hash table may have been empty when the original call was made, that same hash table can be full of data by the time the original call has finished executing.

Implementing Memoization

To pass the hash table along, we modify our function to accept two arguments, with the hash table as the second. We call this hash table, memo, as in memoization:

When calling the function the first time, we pass in both the number and an empty hash table:

Each time fib calls itself, it also passes along the hash table, which gets filled up along the way.

Here’s the rest of the function:

Let’s analyze this line by line.

Again, our function now accepts two parameters, namely n and the memo hash table:

First off, the base cases of 0 and 1 both automatically return n and are unaffected by memoization.

Before making any recursive calls, our code first checks to see whether fib(n) has already been calculated for the given n:

(If the calculation for n is already in the hash table, we simply return the result with return memo[n].)

Only if the calculation for n has not yet been made do we proceed with the calculation:

Here, we store the result of the calculation in the memo hash table so we never have to calculate it again.

Also note how we pass memo along as an argument to the fib function each time we call it. This is the key to sharing the memo hash table across all the calls to the fib function.

As you can see, the guts of the algorithm remain the same. We’re still using recursion to solve our problem, as the computation of fib is still essentially fib(n - 2) + fib(n - 1). However, if the number we’re computing is new, we store the result in a hash table, and if the number we’re computing was already computed once before, we simply grab the result from the hash table instead of computing it again.

When we map out the recursive calls in our memoized version, we get this:

In this diagram, each call that is surrounded by a box is one in which the result was retrieved from the hash table.

So what is the Big O of our function now? Let’s look at how many recursive calls we make for different types of N:

We can see that for N, we make (2N) - 1 calls. Since in Big O we drop the constants, this is an O(N) algorithm.

This is an incredible improvement over O(2^N). Go memoization!