Decoding a DP Problem

Dynamic Programming aka DP is a design technique in computer science, mathematics and bioinformatics to solve complex problem by breaking it into sub problems. It is one of the most powerful methods to solve optimization problem exhibiting exponential run-time complexity (via brute force) in polynomial time at cost of some extra memory space.

This technique was first invented by Richard Bellman and he gave it the name “Dynamic Programming” as he did not want to reveal his work while he was working on it. There is nothing dynamic in a DP technique; it simply called so because its inventor coined this name for it. However the word ‘Programming’ is due to the fact that it is like a tabular method to solve a problem similar to linear programming.

Many of us would have read about DP during our graduation but every time we get a new problem that could be solved using DP we stumble. Why is so? This is because formulation of a problem as a DP problem is most crucial and hardest step in finding the correct solution for it. In this post I would like to explain my takeaways after reading/solving some of the DP problems. I will try to explain some steps or techniques with which we can first understand that the given problem is a DP problem, then formulate it using a recursive relation and finally solve it using the DP(tabular) approach. But before going any further I would like to list the two Hallmark property of a DP problem.

1. Optimal Substructure

A problem can be called to exhibit an optimal substructure property if  “An optimal solution to the problem instance contains optimal solution to its Sub problems”

Let’s take an example of Matrix chain multiplication. 

We are given a chain of Matrices of amicable dimensions to multiply. For Example.

Here the order in which we multiply the matrices will give different number of calculations required to compute the final product.

For example if we multiply in order ((M1XM2)X(M3XM4)) we will need 10x20x30 + 30x15x40 + 10x30x40 = 36000 calculation. Similarly if we multiply (((M1xM2)xM3)xM4) we will need 16500 calculations. We clearly see that there is a big difference in the calculations required.

So how will we find the correct ordering of the multiplication to get the least number of calculations?

This is problem can be solved using brute force by trying out all possible combination in exponential time but we need a polynomial time algorithm. DP is here to help. But to apply a DP algorithm we need to be sure that a sub problem of this problem is optimal. In other words if we consider a matrix sequence M1,M2 and M3 and then if we are sure that solution for M1 to M3 is also contained in solution of M1 to M4 then sub sequence M1 to M3 exhibit an optimal sub structure property.

We can either prove this by Induction or reason it out using contradiction.

Reasoning of Optimal Substructure.

Let’s say

 MCM(i) = Solution for Matrix chain multiplication for sub problem  M1 to Mi where i < n

So if MCM(i) is not included in the MCM(n) then we can always include MCM(i) in the solution and get a better number than MCM(n) which contradicts the assumption that MCM(n) is optimal. Hence MCM(i) will always be included in MCM(n) for all i <= n

2. Overlapping Sub problems

Another Hallmark property of DP problems is that they contain overlapping sub problems.  

To explain this property lets take an example of Fibonacci number generation.

Fib(N) can be defined as

Fib(N)  = Fib(N-1) + Fib(N-2) if N > 2 and Fib(0)=Fib(1)=1

If we create a recursion tree for above problem let’s say for N=5 we get the following.

The overlapping sub problems are color coded with same colors.

if any problem exhibits both the above Hallmark property then there is a good chance that it can be solved using a DP algorithm. That’s what we are going to use to approach and identify is a problem is a DP problem or not.

Difference between DP and traditional Divide and Conquer

DP can also be broadly termed as a divide and conquer algorithm but there is one striking differences. In divide and conquer we keep on discarding the half which is not use full but in case of DP we need to tabulate all the sub problems as well. Hence traditional divide algorithm like binary search, quick sort, merge sort attempt to break the non overlapping problems in sub problems and solve then, due to which their running time complexity is quite good. In case of a overlapping sub problem, if we try to solve them using traditional divide and conquer approach, it will not be efficient as it solves the overlapping problems again and again. The tabulation approach of DP is correct way to go to get a reasonable quick solution.

Difference between DP and Greedy Approach

In dynamic programming we examine a set of solutions to smaller problems and pick the best among them. In a greedy algorithm, we believe one of the solutions to smaller problems to be the optimal one (depending on certain properties of the problem) and don't examine other solutions. 

Steps for Decoding a Dynamic Programming problem.

1.Identify the Hallmark Properties

2.Formulate the problem recursively in terms of Sub problems(Tops down or Bottoms Up)

3.Identify the overlapping solutions and use tabulation to solve the problem bottoms up or tops down with Memoization. 

Let’s take some problems to illustrate the steps.

1. Minimum No of Jumps to reach End from Start

Let’s say we are given an Array A. The number A[i] denotes maximum number of steps that can be taken in forward direction. Now we have to start at beginning and reach the end by taking steps in forward direction. The problem is what will be the minimum no of jumps to reach the end.

Example A[5 4 0 2 7 3 1 9]

We can go to 9 in two jumps 5->3->9 or More jumps 5->4->7->9 etc. 

Step 1: Establish the Hallmark Properties.

1) Optimal Substructure: Let’s say we formulate the problem in such a way that we consider all the positions from where we can reach 9 in 1 jump. In this case they are 7,3,1 Positions. If we know the optimum number of jumps to reach at these problems then our solution will be minimum of such MINJump(7,3,1) so the optimal substructure is guaranteed.

2) Overlapping Sub Problems: The solution for reaching 9 will contain solution for reaching 7,3 and 1. Solution for reaching 1 will contain solution for reaching 4,7,3 Hence there is lot of overlapping in the sub solution space.

Step 2: Formulate the problem recursively.

Now we have seen that Hallmark properties are applicable we can start formulating the problem and start solving it.

Recursive formulation Tops Down & Bottoms Up

Code for recursive formulation bottoms up

// Returns minimum number of jumps to reach array[end] from array[start]

int minimumJumps(int array[], int start, int end)

{

   // Base case: when source and destination are same

   if (start == end)

     return 0;

   // source is a dead end

   if (array[start] == 0)

     return 0xFFFFFFF; //Return a very high value

   // Traverse through all the points reachable from array[start] recursively

   // Get the minimum number of jumps needed to reach array[end] from these

   // reachable points.

   int minimum = 0xFFFFFFF;

   for (int i = start+1; i <= end && i <= start + array[start]; i++)

   {

     int jumps = minimumJumps(array, i, end); //Call recursively and get the minimum for all i

       if(jumps != 0xFFFFFFF && jumps + 1 < minimum)

           minimum = jumps + 1;

   }

   return minimum; //Return the minimum calculated above

}

The above code runs in exponential time as minmumJump is called again and again with several overlapping subproblems. 

Step 3. DP/Tabulation Approach.

For this let us take an array jumps[] of size n and initialize all the values to 0. We run an outer loop for each of the position i and inner loop for each j<i. Then we modify the value of jump[i] if i is reachable from j. Thus when the loops terminate we get minimum no of jumps required to reach a position from start and we can return the value jumps[n-1] as our solution. 

For A[5 4 0 2 7 3 1 9] the intermediate value of jump array are shown below.

0,1,0,0,0,0,0,0, i=0

0,1,1,0,0,0,0,0, i=1

0,1,1,1,0,0,0,0, i=2

0,1,1,1,1,0,0,0, i=3

0,1,1,1,1,1,0,0, i=4

0,1,1,1,1,1,2,0, i=5

0,1,1,1,1,1,2,2, i=6

Here is the code for solving it using DP. minjump.cpp

2. The 0/1 Knapsack Problem

Lets say we are given N objects of weight w[N] and values[N]. We are given a knapsack of weight W. We need to pack these items such that their weight is less than equal to W and their value is maximum.

Establish the Hallmark Properties and Formulate the problem as Sub problem.
1)Optimal Substructure
This problem is also an optimization problem where in we need to either select an item in the optimal selection or we don’t. If we select the current item ’k’,  the maximum weight available would be W-w[k] so we need to find the optimal solution with 0-(k-1) items with weight W-w[k]. So if we have a optimal solution of 0 to (k-1) items then we can always get optimal solution of 0 to k item by either selecting k or not as per weight constraint.
So the formulation of optimal knapsack will be as below.(W is available weight and k is the current element under consideration)

2) Overlapping Sub Problems
We see that we are calling the knapsack with value which are going to overlap with each other. Hence the recursive formulation above will run very slow as it will compute same value again and again. Hence we need to tabulate or memoize the results to avoid doing redundant calculations.

DP Approach:
We need to create a two dimensional table of results for item number in one dimension and available weights in second dimension.
Lets define a Table K[N+1][W+1] where K[i][j] denotes the optimal value by selecting items upto i when the knapsack size is j. We start by initializing K[i][j]=0 when i=0 or j=0;
We start the outer loop for each element i from 0 to N. Then we start an inner loop for getting the optimal solution for each weight from 0 to W. If the current item cannot be selected then we will look at the optimal solution till i-1 with weight w. If it can be selected then we will look at the optimal solution till i-1 with weight W-w[i] plus the value of current item or we lool at optimal solution for i -1 with weight W. We select which ever is maximum and proceed.
The code for DP is here: knapsack.cpp

Example illustration:
Let’s say or Weights W[]= {1,3,2,4,5} And Value[]={10,20,15,30,40} And Weight = 10. We get the following Table:

Lets say example of 45(marked red above) to understand the way to read this table. If we have a knapsack of weight 6 and we are given items upto 10 to 30 then maximum value we can extract is 45 which in turn is max of cell(6,15) and cell(2,15)+30. The last row gives values of optimal solution for different sizes of knapsack for all elements.  And the answer to original problem is the last element of the table ie 80.

3. Towers of Hanoi

We must have heard about this problem many times. The problem definition is simple.

There are three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.

3. No disk may be placed on top of a smaller disk.

Lets examine the solutions to it. We can use a recursive approach to solve this problem by formulating the problem in following way.

Steps: Establish the Hallmark properties

Optimal Substructure

We can see that if we can move the N-1 disks from src to dest tower using the temp tower, then we can move the Nth disk as well by first moving the the N-1 disk to tmp tower and then mving the Nth disk to Dest tower and then moving back the N-1 disks to tmp tower. Hence if we have solution for N-1 then we will also have solution fo Nth disk as size of disk N > all disks upto N-1.

Hence the problem exhibits optimal substructure property.

Overlapping Sub Problems

When we draw the recursion tree as shown below and mark the overlapping solution with same color. We will see that lot of sub problems are repeated along the sub branches. Hence the problem also exhibit overlapping sub problem property. 

The DP Approach

The above approach naturally is exponential in time complexity. And we can use DP to solve it more efficiently. We can create a 2 D table where each row will mark the disk number denoting the solution for N disks. The column will consist of one of 6(3!) possible permutation for (0,1,2) .

We can start filling in Table[N][One of 6 permutation from N=1] from bottoms up and can then use the solution for N-1 row to fill in the next row. Each element of the table will give a string that will contain the steps to follow to solve the movement of that number of disks from the marked src to destination. And the answer will be table[N][0,1,2]th element.

The source code for solving towers of Hanoi using DP can be found here: towHanoiDP.cpp

The following tables gives the moves encoded in number(1,2,3,5,6,7) 

Table

N	1(0,1,2)	2(0,2,1)	3(1,0,2)	5(1,2,0)	6(2,0,1)	7(2,1,0)
1	1	2	3	5	6	7
2	217	125*	536	352	763	671
3	1251671	2172352	3523763	5365125	6716536	7637217
4	21723521 7637217	12516712 5365125	53651253 6716536	35237635 2172352	76372176 3523763	67165367 1251671

125* Means for N=2 disks and to move disk from 0 to 2 via 1 we need the following Moves((0,1,2),(0,2,1) & (1,2,0)) for 1 disk.

Conclusion

In this post I tried to take few problems which can be solved using dynamic programming approach and tried to illustrate the steps involved in first understanding and then solving such problems. My aim was to let the readers understand that for any given problem if they are thinking that it could be solved using DP then first evaluate the two properties. First get non optimal solution using recursion and then try to formulate the problem into a way of tabular deductions where the solution for previous row and columns can be used to get the solution for current row or column. I thank all the readers for going through this post and hope it is useful. 

Take care..