A Tutorial on Dynamic Programming in C++

Now that a number of people have asked me for some good resources on Dynamic Programming (DP) and I could find only a few good resources to give the beginners a real boost, I decided to write this basic DP tutorial here. But before we go deep into it, I want to make it clear that the only way to master DP is a lot of practice. The more you solve, the better you get.

DP is an art. It’s a way of thinking. It’s more like learning to see the same thing from a different perspective. It takes some time to get used to, that’s why practicing without getting disheartened is the key to mastering DP.

Prerequisites for this tutorial are, the knowledge of

1. iteration over (multidimensional) arrays,
2. recursion,
3. basic knowledge of mathematical notations.

An important tip

When you are given a problem to solve using DP, the trick is “Not to over-think, because the solution is always hidden in the problem”. Most beginners make this mistake of thinking too much, only because they thought the problem was difficult and only a complex solution would solve it. But in most cases the solution turns out to be simple.

Before you start coding, formulate the problem (not the solution) mathematically on a piece of paper. Because a problem well formulated is a problem half solved.

For example, let’s consider a simple problem.

THE PROBLEM

I am to count from 1 to N. But I follow a special rule of counting, I can count either 2*x or 3*x or x+1 after I count x. I always start counting from 1. Now what is the minimum number of steps required to count to N.

Here is the example of this counting : If I want to count till 7, I can count like the following:

1 2 3 4 5 6 7
or 1 2 4 5 6 7
or 1 2 3 6 7
or 1 3 6 7
or 1 2 6 7

In this case the minimum number of steps is 4.

ANALYSIS

Now let’s analyze this problem. Here we are asked to choose which number to count after x, such that we will reach N in minimum number of steps. Notice that, we are presented with a choice at a point and we have to make the choice in such a way that our current choice combined with our subsequent choices will give us the optimal result.

You might be tempted to think that the fastest way to reach N would be to count x*3 after x whenever possible. If x*3 > N, then try to count x*2 and if x*2 > N, then count x+1. That’s the greedy way to solve this problem. And this greedy algorithm does not always work. For example if I am to count till 8, the greedy way will be to count like 1 3 6 7 8 (5 steps). But the optimal way would be 1 2 4 8 (4 steps). Another example, count till 13 : greedy way 1 3 9 10 11 12 13 (7 steps), optimal way 1 3 6 12 13 (5 steps).

Now that we have established greedy algorithm won’t work here, let’s analyze why it does not work. It does not work, because we when we assumed that counting x*3 and x*2 and x+1 in the preferential order will solve the problem, we did not consider the effect of making a greedy choice on our subsequent choices.

Before we solve this problem, let's formulate the problem statement mathematically.

Let f(x) = minimum number of steps required to count to x.

f(x) = 1                                        when x = 1
f(x) = min( f(x-1) , f(x/2) , f(x/3) ) + 1      when x > 1

It means, if we have already counted till x-1 or x/2 or x/3, then we can reach x in just one step. We just have to find out whether it's faster to reach x-1 or x/2 or x/3. If x-1 is faster to reach than x/2 and x/3, then counting to x-1 and the counting x will definitely take less steps than counting to x/2 then x, or counting to x/3 then x.

if x%2 != 0, we do not consider f(x/2) in the above expression, if x%3 != 0 then we do not consider f(x/3) in the above expression. Because if x%2 != 0, then x/2 would not be an integer and f(x) is defined only for integers. Same for f(x/3).

SOLUTION

As we can see, the function f is a recursive function. So, we can simply implement it as a recursive function in our language of choice and it should work correctly. But pure recursion will be slow when N is large.

Let’s see, why pure recursion would be slow. Suppose I want to find f(7).

f(7) = f(6) + 1    [as 7/2 and 7/3 are not integers]
f(6) = min ( f(5), f(3), f(2) ) + 1
f(5) = f(4) + 1
f(4) = min ( f(3) , f(2) ) + 1
f(3) = min( f(2), f(1) ) + 1
f(2) = f(1) + 1
f(1) = 1

As we can see, in pure recursion, we will have to calculate f(3) and f(2) more than once. First during f(6) we call f(5) and it calls f(4) which calls f(3) and f(2). When f(4) and f(5) have returned and we are back in the function call for f(6), we call f(3) and f(2) again. Computing same values more than once makes pure recursive solution slower than it needs to be.

But what if we calculate the values of f(x) when needed for the first time and store it in an array and the next time it’s needed we simply look up the array and return the value without really calculating it all over again ? That would be a much faster way to calculate f(N). And this way is known as memoization or top-down DP.

Here is the above idea implemented in C++ like pseudo code:

int memory[N+1];    // global array, all values initialized to 0
memory[1] = 1;      // because f(1) = 1

int f (int x) {
     /* if f(x) is calculated and stored in memory, i.e the value in memory[x]
        is not the default value 0, then just return it without calculation */
      if ( memory[x] != 0 ) return memory[x];

      /* otherwise calculate it recursively */
      int result = INFINITY;
      if (x%2 == 0) result = min (result, f(x/2)); 
      if (x%3 == 0) result = min (result, f(x/3));
      result = min (result, f(x-1) );
      result = result + 1;

      /* now store the result in the array for future use and return */
      memory[x] = result;
      return result;
}

Makes sense ? If not, pause a bit here and read the pseudo code above. Try to imagine how it works during subsequent calls.

Just being able to solve a problem using top-down DP or memoization is enough in most of the cases. But, when the dataset if too large, the number of recursive calls might result in a function call stack overflow. Normally reported as a case of SIGSSEV, more commonly known as segmentation fault. Hence it’s important to learn how to solve the DP problems without recursion.

Before we convert our recursive solution into an iterative one, let's make a few observations about the function f.

1. value of f(x) can never exceed x, i.e. f(x) <= x
2. if we know f(x) <= y, we can say f(x+1) <= y+1, f(x*2) <= y+1 and f(x*3) <= y+1
3. value of f(x) can not be determined with certainty untill values of f(x/3), f(x/2) and f(x-1) have been determined.
4. initially only f(1) = 1 is determined.

Let's use these observations to write an iterative solution (in C++ like pseudo code)

int f[N+1];    // initalize an array to store values of f(1), f(2) ... f(N)

void iterativeDP () {
    for (int x=1; x<=N; x++) f[x] = x;      // Initially assume that f(x) = x

    // when we have determined f(x) update values of f(x+1), f(x*2) and f(x*3)
    for (int x=1; x<=N; x++) {
        if (x+1 <= N) f[x+1] = min (f[x+1], f[x]+1);
        if (x*2 <= N) f[x*2] = min (f[x*2], f[x]+1);
        if (x*3 <= N) f[x*3] = min (f[x*3], f[x]+1);
    }
}

So, that's that and we just solved the problem using DP in both top-down (recursive) and bottom-up (iterative) methods.