An Intro to Dynamic Programming, Pt. I
Dynamic programming is notoriously difficult. Even when you understand the conceptual process (which, by itself, is not that complicated), identifying where to apply it and how to implement it in code can be a real challenge. But it’s important to know about nonetheless, because it can significantly improve the performance of algorithms that use it. And it doesn’t have to be so intimidating! Like any skill, all it takes study and practice… and before you know it, what was once daunting becomes trivial. So for your benefit (and mine!), let’s see if we can better our understanding of dynamic programming: what it is, and how to use it.
What Is Dynamic Programming?
First, a fun fact: the name dynamic programming (hereafter referred to as DP), doesn’t actually mean anything. DP was invented by the mathematician Richard Bellman, who came up with the term because he needed to hide the nature of his work from the secretary of defense due to the secretary’s “pathological fear and hatred of the word research”. Thus, he decided on ‘dynamic programming’ because, in his words, “it’s impossible to use the word, dynamic, in a pejorative sense”, and it’s “something not even a congressman could object to”. Basically, DP is called what it is just because it sounds cool.
But if we can’t draw any meaning from the name, what is DP then, exactly? To quote Wikipedia, which has an excellent definition:
Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.
The process of solving a problem by breaking it down into simpler versions of itself is known as recursion. Likewise, the process of storing the results of these subproblems so they don’t have to be computed more than once is referred to as memoization.
These two concepts are integral to dynamic programming. But I would argue that there’s a third aspect to dynamic programming as well, namely that of guessing. DP is often used for optimization problems where you have to find the best path from point A to point B. Calculating this involves trying many different paths, where at every juncture the algorithm must ‘guess’ which direction to go in, until it eventually tries them all. For this reason, DP is known as a brute force method, albeit a smarter, more efficient approach to it.
So in summary, dynamic programming = recursion + memoization + guessing.
The Fibonacci Sequence
That’s all well and good in theory, but how does it actually work? As a beginner to DP, the first example you’ll inevitably encounter is the fibonacci sequence. This is for good reason — the fibonacci sequence is familiar to most people, and calculating it using DP is fairly straightforward. Thus, it’s an excellent place to start.
As you probably know, the value of the nth item in the fibonacci sequence is equal to the sum of the two values prior to that item in the sequence. In other words:
fib(n) = fib(n − 1) + fib(n − 2)
This is a classic example of recursion. We start with our base cases, fib(0) = 0 and fib(1) = 1, and beyond that the value of every call to fib is equal to the sum of two calls to fib for the terms that precede it. In code, the implementation of this function might look something like this:
Easy peasy. But is this a good approach? When asking this question, I find that it can be helpful map out the algorithm’s recursion tree, so you can really see what’s going on:
The runtime for this algorithm is not good, to say the least. Its time complexity is approximately 2ⁿ, or exponential time (more like 1.6ⁿ actually, since one side of the tree is shorter than the other). This is manageable while our value for n is relatively small, but it will quickly balloon and this methodology will become unfeasible. Try running this to calculate the value of the 50th fibonacci number, and your program will hang for a good minute (the value will also overflow the bounds that an int value can represent, but that’s a separate problem).
There’s a better way to do this. Look closer and you might notice that we’re calculating a lot of these values more than once.
Is it really necessary to calculate fib(2) five separate times? You bet not! Instead, after we calculate it the first time, we can simply store the calculated value in a HashMap or array… in other words, we can memoize it. Then, the next time time we need to find this value, we can just retrieve it from storage, a process which takes constant time (0(1)).
By following this approach we can effectively remove most of the recursive calls from the tree. The result looks something like this:
What a difference! Using dynamic programming, we have enhanced our algorithm to have a linear time complexity of just O(n), a massive improvement over the exponential time complexity we had before. (Believe it or not, this is still not actually the fastest way to calculate a number in the fibonacci sequence — there are other methods that take only logarithmic time).
How would you actually go about implementing this in code? Well, let’s write it out:
This is basically the same thing as we had before, except that we’ve added an array, int[] memo, into which we insert the result for a particular value of n. Now, before calculating a result via recursive calls to fib, we first check to see if a result for a given number already exists. (The check is for zero because when an array is instantiated in Java, it is filled with zeros. Keep in mind that since arrays in Java are statically sized, you’d need to initialize this array with a size of n + 1.)
And there you go! Your very first dynamic programming algorithm!
Top-Down vs Bottom-Up
The version of DP we just implemented is known as top-down dynamic programming. It’s called this because if you look at the recursion tree depicted above, we’re starting from the top of the tree and recursing our way downward. But this is actually not the only way to implement dynamic programming. We can also work from the bottom up.
With bottom-up dynamic programming, instead of recursing, we start by adding the base cases to the memo, and calculate each subsequent value according to the values stored in the memo until we reach our target. In practice, it might look something like this:
Note that this does the exact same amount of computational work as the top down version… we’re basically just accomplishing a recursive task through iteration. This approach has some advantages. For one thing, the run time is more obvious this way — since we’re using a single for loop, it’s fairly straightforward to see that our time complexity is going to be linear.
Another benefit to this approach is that it affords us the opportunity to improve the algorithm’s space complexity, because we don’t actually need to store all the values in our memo. Instead, we can just store the last two items, since that’s all we need to calculate the next item in the sequence. This is demonstrated below:
In this way, we can effectively reduce the space complexity of our algorithm from O(n) (as it was with all prior versions, due to either the the size of the call stack or the size of the memo), to constant space, or O(1).
Conclusion
This was a deep dive into what is ultimately a very simple problem. By doing so, we were able to familiarize ourself with the fundamentals of dynamic programming, getting to know the tools we’ll be using to tackle more interesting problems down the road. Next time, we’ll get into a more complicated example and explore how we can use DP for optimization and finding longest/shortest paths. Stay tuned!
