Recently I have had several conversations regarding Dynamic Programming (DP) and related ideas with colleagues, so thought a post here might be in order.
Technique, Applicability, Example
Dynamic programming is a problem solving technique where a problem is broken down into simpler pieces, one or more of which recur. These smaller problems are easier to solve, and once solved, these solutions can be reused and the various parts can then be put together in clever ways to solve the larger problem we started with. The excellent algorithms text by Cormen, Rivest et al [CLRS] covers this in great detail.
Solving problems that fall into this class typically leverages ideas like memoization (remembering the solutions of smaller sub-problems already solved), recurrence relationships, and recursion. A typical oft-cited example is the Fibonacci series of numbers which starts 0, 1, 1, ... and each subsequent term is the sum of two previous ones. From this, the recurrence relationship is easily derived to be:
Fib(n) = Fib(n-1) + Fib(n-2) with Fib(0)=0, and Fib(1)=1. (In this case the recurrence relationship is obvious. For some problems it might not be, and might take some more work to figure out.)
Fibonacci coded as a simple recursion without memoization struggles to calculate even the 40th number in the series. This is an example of a case where the power of algorithms becomes immediately tangible. The code with memoization on the other hand returns the desired answer almost immediately.
# fibonacci series expansion without memoization
def fib2(n):
if n==0: return 0;
elif n==1: return 1;
else: return fib2(n-1)+fib2(n-2);
# fibonacci series computation with memoization
f={0:0,1:1}; # set up the initial dictionary
def fib(n):
if n in f: return f[n]; # if already computed, return it
if n-1 in f and n-2 in f: # if not already computed, but needed terms available,
f[n]=f[n-1]+f[n-2]; # compute needed number, store it, then return it.
return f[n];
return fib(n-1)+fib(n-2); # use the recurrence relationship.
Why does memoization work? Because it remembers calculations that were already done, and instead of recalculating things, just uses these answers again... returning the desired answer almost immediately. For instance, the code without memoization computes Fib(5) as Fib(4)+Fib(3), then compute Fib(4) as Fib(3)+Fib(2), and so on, and the tree of function calls it completes to calculate Fib(3) are repeated all over again in the tree of function calls to compute Fib(4). In contrast, the code with memoization computes each Fibonacci number just once, stores the results in a hash-table, then reuses these as needed.
In other words, the naive algorithm is exponential in complexity terms, while the memo-ized version runs in polynomial time. This is an important distinction. I particularly love this example because this drives home the idea of the importance of algorithmic complexity in directly observable terms (just see how long one takes to compute numbers vs the other), even for an audience of lay-persons.
If at first you don't succeed... try, try again
"Insanity is doing the same thing again and again and expecting different results"
-- Albert Einstein
But wait! Even the code with memoization has some issues, one of which is discussed below. Why does the first attempt to compute fib(3000) fail, but the same call succeed later?
fib(1000);
fib(3000); # gives a RuntimeError: maximum recursion depth exceeded
# but then try
fib(1500);
fib(1800);
fib(2000);
fib(2300);
fib(2600);
fib(2800);
fib(3000); # this works!
This is because in the first instance, the space between the already computed Fibonacci numbers (fib(1000)) to the target Fibonacci number (fib(3000)) is sparse. The number of recursive calls needed to bridge this gap in the memoization table is too large in one go. However, it is possible to work towards that gap by computing more and more numbers in the interim (say a gap of 300-600 each time) till the target is reached. Each of these intermediate calculations further populates the hash table until we can easily compute the desired number.
Does this negate Einstein's famous (and possibly apocryphal) quote? Probably not. Because the second invocation of fib(3000) is not the same as the first. The system is in a different state when it encounters the second call given all the intermediate computations that were completed in the interim.
The Path Forward
Understanding DP is critical to solving many problems asked in software engineering reviews, such as the following. The more impressive candidate however, is generally one that can look at somewhat more complicated problems, de-construct them into simpler sub-problems that are susceptible to DP methods, devise a solution for those, then put those solutions back together to answer the original seemingly intractable problem.
Typical interview questions - most of these can be easily solved using recurrence relations:
Technique, Applicability, Example
Dynamic programming is a problem solving technique where a problem is broken down into simpler pieces, one or more of which recur. These smaller problems are easier to solve, and once solved, these solutions can be reused and the various parts can then be put together in clever ways to solve the larger problem we started with. The excellent algorithms text by Cormen, Rivest et al [CLRS] covers this in great detail.
Solving problems that fall into this class typically leverages ideas like memoization (remembering the solutions of smaller sub-problems already solved), recurrence relationships, and recursion. A typical oft-cited example is the Fibonacci series of numbers which starts 0, 1, 1, ... and each subsequent term is the sum of two previous ones. From this, the recurrence relationship is easily derived to be:
Fib(n) = Fib(n-1) + Fib(n-2) with Fib(0)=0, and Fib(1)=1. (In this case the recurrence relationship is obvious. For some problems it might not be, and might take some more work to figure out.)
Fibonacci coded as a simple recursion without memoization struggles to calculate even the 40th number in the series. This is an example of a case where the power of algorithms becomes immediately tangible. The code with memoization on the other hand returns the desired answer almost immediately.
# fibonacci series expansion without memoization
def fib2(n):
if n==0: return 0;
elif n==1: return 1;
else: return fib2(n-1)+fib2(n-2);
f={0:0,1:1}; # set up the initial dictionary
def fib(n):
if n in f: return f[n]; # if already computed, return it
if n-1 in f and n-2 in f: # if not already computed, but needed terms available,
f[n]=f[n-1]+f[n-2]; # compute needed number, store it, then return it.
return f[n];
return fib(n-1)+fib(n-2); # use the recurrence relationship.
Why does memoization work? Because it remembers calculations that were already done, and instead of recalculating things, just uses these answers again... returning the desired answer almost immediately. For instance, the code without memoization computes Fib(5) as Fib(4)+Fib(3), then compute Fib(4) as Fib(3)+Fib(2), and so on, and the tree of function calls it completes to calculate Fib(3) are repeated all over again in the tree of function calls to compute Fib(4). In contrast, the code with memoization computes each Fibonacci number just once, stores the results in a hash-table, then reuses these as needed.
In other words, the naive algorithm is exponential in complexity terms, while the memo-ized version runs in polynomial time. This is an important distinction. I particularly love this example because this drives home the idea of the importance of algorithmic complexity in directly observable terms (just see how long one takes to compute numbers vs the other), even for an audience of lay-persons.
If at first you don't succeed... try, try again
"Insanity is doing the same thing again and again and expecting different results"
-- Albert Einstein
But wait! Even the code with memoization has some issues, one of which is discussed below. Why does the first attempt to compute fib(3000) fail, but the same call succeed later?
fib(1000);
fib(3000); # gives a RuntimeError: maximum recursion depth exceeded
# but then try
fib(1500);
fib(1800);
fib(2000);
fib(2300);
fib(2600);
fib(2800);
fib(3000); # this works!
This is because in the first instance, the space between the already computed Fibonacci numbers (fib(1000)) to the target Fibonacci number (fib(3000)) is sparse. The number of recursive calls needed to bridge this gap in the memoization table is too large in one go. However, it is possible to work towards that gap by computing more and more numbers in the interim (say a gap of 300-600 each time) till the target is reached. Each of these intermediate calculations further populates the hash table until we can easily compute the desired number.
Does this negate Einstein's famous (and possibly apocryphal) quote? Probably not. Because the second invocation of fib(3000) is not the same as the first. The system is in a different state when it encounters the second call given all the intermediate computations that were completed in the interim.
The Path Forward
Understanding DP is critical to solving many problems asked in software engineering reviews, such as the following. The more impressive candidate however, is generally one that can look at somewhat more complicated problems, de-construct them into simpler sub-problems that are susceptible to DP methods, devise a solution for those, then put those solutions back together to answer the original seemingly intractable problem.
Typical interview questions - most of these can be easily solved using recurrence relations:
- Devise the most efficient means of finding the largest internally increasing or decreasing sub-sequence given a list of numbers. What are they? How many exist? How long are they?
- Demonstrate how to find the largest common sub-sequence given two sets of numbers or letters. A good interviewer will ask you both to indicate the size of the largest sub-sequence as well as give him the list of all sub-sequences that meet his criteria.
- In how many ways can you make change for $x, using coins with various denominations.
- In how many ways can you partition a number K using positive integers <=K? e.g. 5=1+4=1+1+1+3=2+2+1 etc.,
