Introduction to Dynamic Programming using a C Program Example

Dynamic programming approach was developed by Richard Bellman in 1940s.

It was an attempt to create the best solution for some class of optimization problems, in which we find a best solution from smaller sub problems.

This approach is recognized in both math and programming, but our focus will be more from programmers point of view. This is not an algorithm that could be applied to all problems of optimization.

Dynamic Programming Definition

To start with it, we will consider the definition from Oxford’s dictionary of statistics.

“The problem of optimization a sequence of decisions in which each decision must be made after outcome of the previous decision becomes known”

If we stop for a second, and think what we could figure out from this definition, it is almost all we will need to understand this subject, but if you wish to become expert in this filed it should be obvious that this field is very broad and that you could have more to explore.

What is Dynamic Programming?

Some authors will consider only bottom up approach as suitable for dynamic programming, but some will also accept the top-down approach as well.

In our example program, we will use the bottom-up approach with a table, which will be implemented in an array. You can also use a matrix instead of array, which might occupy more space in the memory.

So, our algorithm will be also optimized from memory usage point of view as well.

Now we will create small digression, in order to understand the conditions that we need to satisfy, to apply this approach of solving multi level decision making, with iterative formula that works in bottom-up manner, which would ultimately lead us to the best solution.

In dynamic programming, the bigger problem gets broken into smaller problems that are used to create final solution. In each step, we need to find the best possible decision as a part of bigger solution.

It is important to calculate only once the sub problems and if necessary to reuse already found solutions and build the final one from the best previous decisions. Previous decisions are kept in the matrix or an array.

This way we will have fewer calculations, then purely combinatory approach that would consider all possible permutations in order to pick the optimum, and as a result of this approach it will lead us to algorithm of pseudo polynomial speed.

Two Conditions for Dynamic Programming

As we have said before, the big problem has to be broken into simpler steps, but to apply this approach you need to have two conditions:

1. Overlapping sub problems which are smaller
2. Optimal structure

Overlapping smaller sub-problems: The first condition means that we are dealing with overlapping sub problems if one bigger problem could be divided into smaller problems that are less complex and could be reused in calculations so that repeated calculations are evaded or that recursive algorithm for particular problem solves same problems more times, instead of generating new sub problems all the time.

To illustrate this, we could have Fibonacci sequence or binomial coefficient.

The recursive formula, as we know from before, for Fibonacci sequence is F(n) = F(n-1) + F(n-2). As we could observe, one element gets calculated from two previous, and some calculations are repeated, this could be noted with graph structure as well.

If you calculate the binomial coefficient you would use recursive formula: n over k is equal to n-1 over k-1 plus n-1 over k.

Optimal structure: The second condition means that optimal solution of higher level could be calculated from previous stages with some iterative formula. This way, at each stage we chose the optimum solution, and afterwards that stage might be useful in next decision making.

Sometimes, we should consider problem of possibility to solve certain problem, but in our problem we will not discuss it. It is important to figure out if solution is possible as well.

If you are trying to construct n-th element of Fibonacci sequence it is obvious that you will be able to do it so, but in some problems like measuring the weight of an object or some other problem, it is not so obvious that you could construct such a solution.

Then you have some results from number theory or rule of thumb. For example, if you try to measure weight of 7 with weights of 5 and 3, you would not be able to achieve this task.

Next thing that could be considered is the problem of unique solution or multiple solutions. Sometimes, one problem could have few solutions, 1+1+4+6=12 or 2+2+2+6 that are of same number of numbers. In dynamic programming approach it is usually important to get one solution.

If you are not sure could you apply this method, you could still create some algorithm that will have solutions checked for all possible permutations of the set, and then if you find that solutions are same as the ones from DP approach you could be pretty sure that DP is applicable. Yes, this is not a proof from mathematical point of view, but it is good enough in practical applications. It is a reason some programmers spend so much time testing their algorithms.

Problem Definition

In this article, we’ll solve the following problem using a C program example.

A big stone has mass of N. This weight is measured as a whole number. This is a number that is suitable for unsigned int data type. In our solution, we will assign this type to this object.

You also have infinite number of stones with mass: 1, V2, V3…Vk.

These smaller weights would be used to measure big weight.

This way, we could always measure mass N, as a sum of N*1, but our task is to find the minimum number of small stones that would measure the weight N and to present one of the possible breaking of big weight N that gets broken into sums of smaller weights.

In another words you will not care if weight N could be made in few ways.

Solution to the Problem

Because this is not trivial solution, we will discuss the algorithm for N=15 and small weights: 1, 4, and 7.

One very important step is the solution for a trivial problem.

If you have the weight of 0 you have 0 small stones that will add up to weight of 0.

If you have weight of 1 the only possible solution is one stone of weight 1, this decision is made after weight of 0 is measured. Then, if we consider weight 2 it could be formed as sum of two weights of 1. For the weight of 3 we would have tree stones of weight 1. If the weight of big stone is 4, the best solution is to pick one stone of weight 4, and this would be created after trivial solution is used as base for this step. The weight of 5 could be achieved as 4+1, this way you get solution for 5, as a base you use previous decision which is one stone to get the weight of 4.

The weight of 6 is created as 1+1+4. Next one is measured as one rock of weight 7. The weight 8 could be formed like two stones of weight 4 or two stones of weight 1 and 7. This will not be important because those solutions would have same number of stones. Now I will skip few steps, but I would recommend you to calculate them for you self in the text book or in some program that you personally prefer.

Last weight of 15 could be created with tree stones one of weight 1 and two stones of weight 7 or 2*4+7. About second solution we will not care in this program.

So, the weight of 15 is reached from weight of 14 if we add one stone of weight one, the weight of 14 is formed if we add one stone of weight 7 to one stone of weight 7 that is necessary to form a weight of 7, and this weight is achieved from trivial solution.

To keep the track of this we will have few arrays, and one formula that will be used to calculate best decision in each step of the algorithm.
Formula we use in this case is:

When we consider a weight of j stone, as a potential part of the best solution for the final weight, we are searching for a minimum number of weights that will form particular sub weight. Those weights are calculated from previously found best solutions and all small weights that could potentially form a required big weight.

If you build the solution from previous solutions, you will be able to form a final weight with minimum number of stones and you will be able to disassemble that final weight into sum of minimum number of smaller rocks.

C Program Example for Dynamic Programming

The above solution is implemented using the following C program example.

/***********************************
This programm uses DP approach.
Weight N will be replaced with 
minimum number of smaller weights
***********************************/

#include <cstdio>
#include <cstdlib>

#define BIG_NUMBER 10000

void setTheValues(int,int*);
void inputValues(int, int*);

int
main()
{
/* w is for small weights*/
/* v is to keep the track of what have we added*/
/* p is to keep track of previous values */
/* min is for minimum number of small weights that would keep sub problems */
int *w,*v,*p,*min;

/* e is to stop the screen */
/* s is the weight we need to reach */
/* n is the number of coins*/
int  e, s, n;

printf("Input the number of small weights->");
scanf("%d",&n);

w=(int*)calloc((n+1),sizeof(int));
v=(int*)calloc((n+1),sizeof(int));
p=(int*)calloc((n+1),sizeof(int));
min=(int*)calloc((n+1),sizeof(int));

printf("Input the big weight to reach->");
scanf("%d",&s);

setTheValues(s,min);

inputValues(n,w);

for(int i=1; i<=s; i++)
  for(int j=0; j<n; j++)
       if(w[j]<=i)
	      if(min[i-w[j]]+1<min[i])
		  {
			  min[i]=min[i-w[j]]+1;
			  v[i]=w[j];
			  p[i]=i-w[j];
		  }

printf("\nThe minmum number of small weights is=%d\n",min[s]);

printf("\nWe have added this small weights!!!\n\n");

for(int j=s; j>0;j=p[j])
	printf("%d+",v[j]);

scanf("%d",&e);

free(w);free(v);free(p);free(min);

return 0;
}

void 
setTheValues(int s, int* min)
{
	*min=0;
	for(int i=1; i<=s;*(min+i)=BIG_NUMBER,i++);	
}

void inputValues( int n, int* w)
{
   int temp;
   printf("Input the values of weights\n");
   *w=1;
  for(int i=1; i<n; i++)
   {
     printf("\nNext value pleas->");
     scanf("%d",&temp);
     *(w+i)=temp;
   }
}

To check if program is working, you should input the number of small weight as 3, the weight to reach should be 15, and small weights should be 4 and 7.

To reach 15 as a weight you should have tree small weights that would add up to required big weight.

The output should be 1 + 7 + 7.

Let’s look at the above program:

• First we defined all the arrays (and some variables) that we use.
• Then, we create arrays that we need
• For s, we have assigned the place for big weight that will be weighted with smaller weights.
• We set some big values for minimum number of changes. It is like we look for the minimum multiple times the first one is for a trivial case.
• After this, we input the small weights that will be used later, don’t forget that the first one is equal to weight of 1.
• Two for loops will be used to find the best sub solutions for each of the problems.
• We will also keep the track of the weights that we will use in our example. This is used to find what are small weights used in sub-decisions.

Additional Exercises for Dynamic Programming

1. Try to measure one big weight with few smaller ones.

• Weights are: 1 and 2.
• Weights are: 2 and 5.
• Weights are: 3, 8 and 11.
• Weights are: 2, 4, 8 and 16.
• Weights are 1, 2, 4 and 16.

2. Solve the knapsack problem in dynamic programming style.

• 0/1 version.
• Infinite number of small objects.

3. Your task is to find how you should spent amount of the money over the longer period of time, if you have some capital to start with. At different years you spend different sums and you will not leave money to your children.

4. Solve egg dropping puzzle in dynamic programming style.

5. From a given set of numbers that is generated, find the longest arithmetic progression.

6. At the two dimensional box, which could be modeled with matrix, you have different products in each cell. You should find the path from lower left corner to upper right corner of the matrix by going up or right. That path should have the most valuable sum. The sums are also known.

7. You are going from top left corner toward bottom right corner and back. In each cell of a matrix it is stored some “points”. Your task is to find the best path with maximum “points” if you are able to go left and down in first round and up and right in second round.