Dynamic programming: a systematic approach

As Wikipedia says: dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler sub-problems, solving each of those sub-problems just once, and storing their solutions.

Apart from being a frequent question in coding interviews, dynamic programming allows to answer seemingly very difficult questions efficiently and with little code. However, the tutorials I read, said little about a systematic approach to solve dynamic programming problems. Here, I line out the steps and apply them to an example problem:

Steps

1. Define a function F that measures the quality of a solution
2. Find the problem state S function F(S) depends on
3. Define a recursive formula for F(S) from simpler states
4. Implement the algorithm
1. Top down: recursive with memoization
2. Bottom up: iterative with tabulation
5. Keep track of the states that resulted in the optimal solution

Example

As an example we will solve the following, common interview question via dynamic programming:

Find the minimum number of coins with values 1, 3 or 5 that sum up to 11.

This question appears in various disguises but always boils down to the finding the minimum number of values that sum up to some target value.

Step 1

"Define a function F that measures the quality of a solution". The problem states that the minimum number is to be found. The quality of a solution is therefore described by the number of coins required (the lower the better):

  F = number of coins

For instance, we can sum up 3+3+3+1+1 (5 coins), or 5+5+1 (3 coins) to achieve 11. The latter solution with 3 coins is obviously the better (actually the optimal) one.

Step 2

The second step is: "Find the problem state S function F(S) depends on". We are looking for a state that F depends upon. In this case the number of coins obviously depends on the target value. For example, if the target value is 1, then only one coin is needed. If the value is 2, then we need two coins (1+1), if the value is 3 then one coin is sufficient again, and so on.

  S = target value (0 to 11)

Step 3

The third step is the hardest: "Define a recursive formula for F(S) from simpler states". What is a simpler state? Here, the smaller the target value the easier the solution. Since we need a recursive formula we always pick the simplest possible state first (target value is zero) and make that the exit/start case for our recursive formula. If the target value is zero (S = 0) then we need no coins at all:

  F(0) = 0

Next we need to compute F(S) from smaller states S. Let's write down some intermediate formula for that:

  F(S) = 1 + F(S_smaller)   with S_smaller < S

We compute F(S) (= number of coins for target value S) by taking F(S_smaller) for some smaller state and adding one coin (remember F is the number of coins and not the target value). Which coin we don't know yet but we know we will need one extra coin to go from S_smaller to S, therefore F(S) = 1 + F(S_smaller).

Let's say we have several smaller states (= target values) to choose from, which one do we pick? It should be the one that requires the smallest number of coins because that way we add the least number of coins to F. Therefore we write:

  F(S) = 1 + min F(S_smaller)
           S_smaller < S

What are the smaller states we can produce. Given a a target value S we can produce a smaller S by taking away a coin (S_smaller = S-c). We have three different coins (1,3,5). We try all three of them and take the one the results in the smallest number of coins. We just have to make sure that S_smaller is never negative (S-c >= 0). With that the complete recursive formula becomes:

  F(0) = 0
  F(S) = 1 + min F(S-c) 
           c in [1,3,5] 
           S-c >= 0

To summarize: If the target value is zero (S=0) we need no coins (F(0) = 0). Otherwise the number of coins F(S) is one coin plus the minimum number of coins (min F(S-c)) we find by taking one of the three coins (1,3,5) away and provided the resulting smaller target value does not become negative (S-c >= 0).

Step 4

From now on things become easy and the implementation almost mechanical. The recursive formula can directly be translated into Python code:

  
def F(S):  
  if S == 0: return 0
  return 1 + min( F(S-c) for c in [1,3,5] if S-c >= 0 )

Note that the recursive solution above is of exponential complexity and not yet a dynamic programming solution, which will implement next.

Step 4.1

For the top down, dynamic programming algorithm we only need to add memoization to the recursive implementation. This is achieved by storing already computed results in a cache and use them if available:

  
fs= {0:0}   #cache
def F(S):
  if S in fs: return fs[S]
  fs[S] = 1 + min( F(S-c) for c in [1,3,5] if c <= S )
  return fs[S]

Note that we can fold in the exit condition for the recursion into the initial value for the cache. I also rewrote S-c >= 0 to the equivalent c <= S, because it is a bit shorter.

Step 4.2

The bottom up solution with tabulation can easily be derived by allocating the cache beforehand and filling it iteratively from the start (bottom up):

  
S_max = 11
F = [0]*(S_max+1)  #tabulation == cache
for S in range(1, len(F)):
  F[S] = 1 + min( F[S-c] for c in [1,3,5] if c <= S)  

Since F[S] is computed from smaller states S we know that F[S-c] will be filled when we need it. We just need to add F[0] = 0 to the beginning of the array to have a starting point.

As for the computational complexity: If you look at the code, you see that there is a single loop depending on the length of array F, which itself depends on the target value S. Computation of min(F[S-c]) is constant for a fixed number of coins and therefore we have linear time complexity.

Step 5

The algorithms above allow us to compute the minimum number of coins that sum up to a given target value. But often we also want to know which coins where used. In general, this is achieved by keeping track of the optimal, intermediate states and their coins, and then tracing back from the end state.

The following code adds tracing to the recursive, top down solution. At each step, we store the coin c_min that was used to produce an optimal solution f_min for state S in a directory cs. The function coins() recursively traces back from the end state (S=11) and returns a list of coins:

  
fs = {0:0}
cs = {0:0}
def F(S):
  if S in fs: return fs[S]
  f_min, c_min = min( (F(S-c), c) for c in [1,2,5] if c <= S )
  fs[S], cs[S] = 1 + f_min, c_min
  return fs[S]
 
def coins(S): return [cs[S]] + coins(S-cs[S]) if S else []    
  
print("minimum number:", F(11))
print("coins", coins(11))

If you find coins(S) confusing, this more explicit but longer version that prints out the coins may help your understanding:

  
def coins(S): 
  if S > 0:
    print(cs[S])
    coins(S-cs[S])

To complete the example let us also add tracing to the iterative solution. It is essentially identical to the recursive algorithm but we store the states and coins in an array instead of a dictionary.

  
S_max = 11
F = [0]*(S_max+1)
cs = [0]*(S_max+1)
for S in range(1, len(F)):
  f_min,c_min = min( (F[S-c],c) for c in [1,3,5] if c <= S)
  F[S], cs[S] = 1 + f_min, c_min
   
def coins(S): return [cs[S]] + coins(S-cs[S]) if S else []    
  
print("minimum number:", F[S_max])
print("coins", coins(S_max))

As you can see, dynamic programming can produce very elegant and short algorithms for complex problems. However, there are two conditions that need to apply: overlapping sub-problems and optimal substructure. The overlapping sub-problems condition is easy to understand. Let us have a look at the recursive algorithm without memoization again and print out the F(S) it computes for a smaller target value of 5:

  
def F(S):
  print("F(%d)"%S, end=" ")
  if S == 0: return 0
  return 1 + min( F(S-c) for c in [1,3,5] if S-c >= 0 )

F(5)

The print out shows that some F(S) are computed multiple times. For instance F(1) is calculated three times:

  
>>>F(5) F(4) F(3) F(2) F(1) F(0) F(0) F(1) F(0) F(2) F(1) F(0) F(0) 

Memoization or tabulation stores already computed solutions and so avoids repeated computation of the same result. If, however, each result is unique and is never used again, the recursive algorithm is as efficient as the dynamic programming approach because caching results saves nothing. For instance, if there is only one coin value no result is repeatedly computed:

  
def F(S):
  print("F(%d)"%S, end=" ")
  if S == 0: return 0
  return 1 + min( F(S-c) for c in [1,3,5] if S-c >= 0 )

F(5)
>>>F(5) F(4) F(3) F(2) F(1) F(0) 

Overlapping sub-problems are required, and the larger the overlap the more efficient dynamic programming via memoization or tabulation becomes compared to recursive or brute force solution.

The second condition of an optimal substructure requires that an optimal solution computed for a smaller state can be used to derive an optimal solution of a bigger state. Otherwise, we cannot come up with a recursive formula that allows us to compute F(S) from smaller states.

A final note: the time and space complexity of the top down and the bottom up algorithms are the same (linear for the coins problem). The top down (recursive) algorithm is easier to derive from the recursive formula but the iterative (bottom up) solution is a little bit shorter and maybe easier to understand.