Pre-requisites: A conceptual understanding of what recursion is, as well as other basic concepts in algorithms like: asymptotic notation, time complexity, and graph traversal.
Dynamic programming is an optimization of recursive solutions by using a cache. If you have a recursive solution (e.g. Fibonacci sequence), then we call it dynamic programming if we make use of a cache to optimize performance. Dynamic programming is a trade-off where we use extra memory to reduce the time complexity by more than a constant factor. For traditional dynamic programming problems, we are forced into this choice by an exponential recursive solution with unacceptable performance. DP is probably fascinating because with a relatively small optimization, exponential recursive solutions are transformed into linear solutions.
Rigorous definitions of dynamic programming often mention a recursive solution defined in terms of smaller subproblems. This is another way of saying that if we with to solve our problem, we need to solve a set of other problems, each of which require that we solve an increasingly smaller set of problems, etc. With a finite set of subproblems, we can compute a solution, but the naive solution is too slow.
The classic example of a dynamic programming problem is computing the Fibonacci sequence. The sequence is 1, 1, 2, 3, 5, 8, 13, 21, … We see that in the general case, we can compute the next element in the sequence by the addition of the two preceding elements in the sequence. So the next element in the above example would be 34 since 13 + 21 = 34. The exceptions are the first two elements, for which we can’t apply this rule since there aren’t enough preceding elements. By definition, these values are said to be one. That is, our Fibonacci sequence is really just two numbers (1 1) and a rule (next number is the sum of the two previous ones). From that alone we get our Fibonacci sequence.
There are two general ways of writing a dynamic programming solution. They are generally called top-down or bottom-up. They are differentiated in how the solution space is traversed. Picture our solution space as a set of geometric points. Each point has a direct mapping to the parameters of the recursive function call. These points have geometric positions so that there is a predictable way to see which other points are the dependent subfunctions of a given function call. For the Fibonacci sequence we can picture a number line, where indices on this number line correspond to that Fibonnaci number in the sequence. Since the 8th Fibonacci number (1 index) is 21, the position 8 on the number line has the value 21.
Top down approach: Here, if we are tasked with solving f(x), we can attempt to solve f(x-1) which requires we try to solve f(x-2), etc. We traverse from right to left through our solution space. Chronologically, we attempt to solve the bigger problems before the smaller problems, even though technically the smaller problems have to finish before the bigger problems finish. If we were to make a sequence of which subproblems we attempted to solve first, we’d have a list of solutions sorted from hardest to easiest.
Bottom up approach: We need to solve f(x), so we start solving increasingly difficult subproblems until we’ve solved for f(x). Here, we traverse from left to right through our solution space. For higher dimensions, we need to be care to choose a way to traverse our solution space so that when we try to solve f(a) for some a, we’ve already started and finished solving all the smaller dependent subproblems. If we were to make a sequence of which subproblems we attempted to solve first, we’d have a list of solutions sorted from low to high.
The top-down method is effectively a DFS traversal of the solution space starting with the original problem you wish to solve. The bottom-up method is a BFS traversal of the solution space starting with the smaller sub-problems and working up towards the larger problem. For our Fibonacci example, a top-down solution will attempt to solve f(x), recurse to f(x-1) and f(x-2) in the general case, and continue recursing through these sub-function calls until it reaches the base case. This is the primary weakness of the top-down approach: Recursive function calls require memory from a source which has fixed limits. If the recursion depth is too deep your program will crash. The bottom-up approach is not susceptible to this problem since it is not expressed in terms of function recursion.
Top-down strengths:
- Easy to write as an extension of the recursive solution.
- Very flexible. No need to specify how to traverse the solution space in higher dimensional cases, since each function call will take care of its dependent subcalls. This means that for higher-level dimensions to your problem, your boilerplate remains the same.
- Has the potential to be much faster than bottom-up approach since you don’t need to compute the entire solution space for every smaller subproblem. Subproblems that don’t matter aren’t computed.
Top-down weaknesses:
- If there are too many levels of recursion when traversing through the solution space, you can easily crash your program. It might require significant work to find ways around this.
Bottom-up strengths:
- Less prone to memory constraints since you cache will be stored on the heap. That is, fewer run-time surprises for a logically correct implementation.
Bottom-up weaknesses:
- You need to compute the entire solution space for every smaller subproblem. In practice, this is a minor tradeoff.
- You need to explicitly state how you will traverse the solution space when computing smaller sub-problems. For higher-dimensional functions this can quickly become very complicated. You cannot use the same template for different dynamic programming problems.
Now let’s talk about what our skeleton code might look like with a concrete example. Let’s use Fibonacci.
int Fibonacci(int x) {
if(x < 2) return 1;
return f(x - 1) + f(x - 2);
}
To convert this to a top-down solution, we pass in a cache by reference as an extra parameter to our function. Then for each function call, we return the value in the cache if the parameter already exists in the cache as a key. If not, then we compute our return value as usual, and store it in our cache before returning.
// top-down DP solution
int Fibonacci(int x) {
static map<int, int> cache;
if(cache.count(x) > 0) return cache[x];
if(x < 2) {
cache[x] = 1;
return 1;
}
int fx = f(x - 1) + f(x - 2);
cache[x] = fx;
return fx;
}
See what I mean when I say DP is just recursion with caching?
Next let's explore the bottom-up solution. Since this is a one-dimensional function, the order that we traverse the solution space is pretty straightforward. We'll compute f(2), f(3), ..., up to f(x).
// bottom-up DP solution
int Fibonacci(int x) {
vector<int> cache(x);
cache.at(0) = 1; // base case
cache.at(1) = 1;
for(int i = 2; i < x; i++) {
cache.at(i) = cache.at(i - 1) + cache.at(i - 2);
}
return cache.at(x);
}
You may have noticed that the cache data type for the top-down and bottom-up solutions were different. In the top-down solution it was a hashset, and in the bottom-up solution it was an array. This difference is inconsequential, though. All that's necessary is some data structure which can act as a hashset. For the one dimensional case, arrays are an obvious candidate. In general I don't use arrays for the top-down approach, even though I could, because hashsets are more flexible when you don't know how much memory you'll be storing. Also, arrays are only useful if you can use the function parameters to construct a unique one dimensional key as an integer type. In C++, the map data structure is very flexible in what it allows as key types, so in the 2D case, the cache would be map<pair<T1,T2>,V>, where T1 and T2 are inputs to the recursive function and V is the value returned by the recursive function. This is what I mean when when I say the top-down approach is more flexible for higher dimensional input than the bottom-up approach. Though while I could just as well use a hashset as the cache for the bottom-up approach, it doesn't sidestep the major problem of needing to know how to traverse the solution space.
In pseudo-code, here are what your templates might look like:
// top-down
f(x)
static cache;
if(x in cache)
return cache[x];
if(base_case_argument(x))
cache[x] = base_case_value(x);
return cache[x];
// compute fx, possibly using recursion
cache[x] = fx;
return cache[x];
// bottom up, 1D case
f(x)
cache[base_case] = base_case_value; // there may be multiple base-cases
for(int i = base_case + 1; i < x; i++)
cache[i] = /* your logic here */;
return cache[x];
So which one to pick?
The short answer is that either is fine, since the run-time complexity will be the same (linear). With that said, it's important to be very comfortable with both methods, since some problems are much more easily expressed in terms bottom-up or top-down. The most important factors that come to mind are (a) how deep does the recursion go from a top-down approach; (b) how much of the solution space is necessary to compute your original problem; and (c) is traversing the solution space manually easy to code?
If the recursion depth is large from a top-down approach, you should go with bottom-up. How much of the solution space you really need to compute is only relevant if computing your function is very, very expensive. If that's the case, top-down will be kinder on your performance by avoiding unnecessary computations. If traversing the solution space is very difficult or challenging, avoid bottom-up unless you have a compelling reason to discount top-down.
It's possible that among the major points of consideration I outlines, more than one is present. In that case you'll need to make trade-offs, but I think that much is obvious.