Tutorial on Dynamic Programming - Part III

This tutorial is in continuation with Tutorial on Dynamic Programming Part I and Tutorial on Dynamic Programming Part II

Can you give me a thorough example of DP? 

Why not! Following is an example of working of Dynamic Programming. It presents a comparative analysis of working of DP with the working of Divide & Conquer.

Let us consider the Coin Counting Problem. It is to find the minimum number of coins to make any amount, given a set of coins.  

If we are given with a set of coin of 1 unit, 10 units and 25 units, then to make 31, how many minimum numbers of coins are required?

Let us check whether the greedy method will work or not. Greedy Method says that just choose the largest coin that does not overshoot the desired amount. So at the first step, we will take one coin of 25 units and then successively in each of next six steps, we will take one 1 unit coin. So ultimately the solution of Greedy Method is 31 = 25 + 1 + 1 + 1 + 1 + 1 + 1 (Total 7 nk!umbers of coins needed)

But evidently there is better solution like 31 = 10 + 10 + 10 + 1 (only 4 numbers of coins are needed). 

Hence Greedy Method will never work.

Now let us check whether any better algorithm exists or not! What about the following?

To make K units:

If there is a K unit coin, then that one coin is the minimum

Otherwise, for each value i < K,

Find the minimum number of coins needed to make i units

Find the minimum number of coins needed to make K - i units

Choose the value of i that minimizes this sum

  

Yes. This will work. This is actually following Divide & Conquer Principle but there are two problems with this. This solution is very recursive and it requires exponential amount of work to be done.

  

Now, if we fix the given set of coins as 1, 5, 10, 21, 25 and if the desired amount is 63, then the previous solution will require solving 62 recursive sub problems. 

What If we think to choose the best solution among?

•   One 1 unit coin plus the best solution for 62 units
•   One 5 units coin plus the best solution for 58 units
•   One 10 units coin plus the best solution for 53 units
•   One 21 units coin plus the best solution for 42 units
•   One 25 units coin plus the best solution for 38 units

In this case, we need to solve only 5 recursive sub problems. So obviously, this second solution is better than the first solution. But still, this second solution is also very expensive. 

Now let us check how DP can solve it!

To make it shorter in length, let us think that desired value is 13 units and the set of coin given is 1 unit, 3 units, and 4 units.

DP solves first for one unit, then two units, then three units, etc., up to the desired amount and saves each answer in a table (Memoization). Hence it goes like

For each new amount N, compute all the possible pairs of previous answers which sum to N

For example, to find the solution for 13 units,

First, solve for all of 1 unit, 2 units, 3 units, ..., 12 units

Next, choose the best solution among:

n   

• Solution for 1unit   +   solution for 12 units
•  Solution for 2 units   +   solution for 11 units
•  Solution for 3 units   +   solution for 10 units
•  Solution for 4 units   +   solution for 9 units
•  Solution for 5 units   +   solution for 8 units
•  Solution for 6 units   +   solution for 7 units

This will run like following

There’s only one way to make 1unit (one coin)

To make 2 units, try 1 unit +1 unit (one coin + one coin = 2 coins)

To make 3 units, just use the 3 units coin (one coin)

To make 4 units, just use the 4 units coin (one coin)

To make 5 units, try

• 1 unit + 4 units (1 coin + 1 coin = 2 coins)
•  2 units + 3 units (2 coins + 1 coin = 3 coins)
•  The first solution is better, so best solution is 2 coins

To make 6 units, try

•  1 unit + 5 units (1 coin + 2 coins = 3 coins)
•  2 units + 4 units (2 coins + 1 coin = 3 coins)
•  3 units + 3 units (1 coin + 1 coin = 2 coins) – best solution

Etc.

Ok. I got it but how could you say that computationally this is the best?

The first algorithm is recursive, with a branching factor of up to 62. Possibly the average branching factor is somewhere around half of that (31). So the algorithm takes exponential time, with a large base.

The second algorithm is much better—it has a branching factor of 5. Still this is exponential time, with base 5.

The dynamic programming algorithm is O(N*K), where N is the desired amount and K is the number of different kinds of coins. 

So I don’t hesitate to say that computationally, DP algorithm works best among these threes.

There is only one part left for this tutorial. In the next post I will be explaining the solution of Matrix Chain Multiplication with Dynamic Programming methods.