This is the third post in Dynamic Programming – Online Classes.
This is another article which demonstrates the usage of dynamic programming to solve a different problem in hand. To learn the basics of dynamic programming check my first article on dynamic programming.
Purpose of the post
The purpose of this article is to solve another problem using dynamic programming, this is a very famous interview question which is asked in multiple interviews. So without wasting any time, let us jump into the problem and ways to solve the same.
Find minimum number of coins which result in a given sum
We are given few denominations of coins, we can use each denomination as many number of times as we want and arrive to a given sum of money. For e.g. we are given denominations 1, 3, 5, 6, 7 and we have to arrive to 100 rupees. Then what is the minimum number of coins which can build up a sum of 100 rupees.
Assumption:The array of denominations is in ascending order. If not you can sort it by any of the sorting algorithms listed here
Also, the denominations are integral.
This question is a classic example of bottom up approach and we will try to solve this using dynamic programming. I am sure this is not very tough and will not be a lengthy article.
We start with calculating the minimum number of coins which can get a sum 1. Then using this information we calculate the minimum number of coins to get a sum 2 and so on. Similarly we can reach to the sum we desire.
Dynamic Programming Solution
As discussed in the previous articles the dynamic programming is a tabular bottom up approach, where we need to find a repetitive sub problem. Here if I try to define the sub-problem what would it be?
Let us say that we have an array of denominations D[a1, a2, a3, …., ai-1, ai, …, an-1, an]. And we are calculating the sum Sk.
Our task is to find the biggest coin which is smaller than Sk. Now suppose we find a coin ap from the denominations array which is the biggest coin smaller than Sk. This means we have already achieved a sum of ap and we only need to achieve the difference Sk – ap.
The way we are solving it, we have already calculated the minimum number of coins required for all the smaller sums. This means that the minimum number of coins required to achieve Sk – ap is already known to us.
Hence the minimum number of coins required to achieve Sk is 1 + the minimum number of coins required to achieve Sk – ap.
In all the problems we solve with dynamic programming, I find it better to define the running time complexity in the following notation O(O(P), O(Q)), where the algorithms mostly have to perform two different types of task. One is called pre-processing and the other is the actual task.
For example, in our present example, building the table an calculating the minimum number of coins required for all the sum is the pre-processing task. After that if I come to you with a bunch of numbers and ask you to give me the minimum number of coins for each one of them, it would be just a look up which can be performed in constant time. If you notice, then this kind of approach may cost a lot for the first query, but for subsequent queries the cost is constant time or O(1).
Hence O(P) is the complexity of the pre-processing and O(Q) is the complexity of subsequent sub-queries. If O(P) takes 1000 seconds and O(Q) takes 1 second each, then over a span of around 5000 queries, the overall cost would be 6000 seconds and that would result in 6000/5000 = 1.2 seconds per query, if the number of queries increases then over a period of time the cost would be 1 second per query, and that would be desirable result.
This process is called amortization, where we amortize the cost of a certain operation and apply a minimal charge to all the consumers. To give a real world example, consider a car renting business, the owner of the business has invested a lot of money in the beginning assume $10000 per car and he has 10 cars. Now if tourists arrive to the city, they would definitely not buy a car for their stay of 10 – 15 days, they would prefer to get something at a cheaper rate. So they approach this car renting service and hire a car for $200 per day. So if a car is hired for 50 days the cost of the car is recovered and the next subsequent hire would be earning a profit.
Hence, amortization is good when we have a huge query set to be executed and the pre-processing doesn’t cost that much which we can’t recover even with maximum numbers of expected queries.