This post is completed by 4 users

  • 1
 Add to List
Medium

145. Dynamic Programming - Minimum Coin Change Problem

Objective: Given an amount of 'A' and n coins,   v1<v2<v3<...........<vn. Write a program to find out the minimum number of coins required to make the change for the amount 'A'.

Example:

Amount: 5

Coins [] = 1, 2, 3.

No of ways to make the change are : { 1,1,1,1,1} , {1,1,1,2}, {2,2,1},{1,1,3} and {3,2}.

So as we can see minimum number of coins required are 2 ( 3+2=5}.

Approach:

For Every coin, we have two options, whether to select it or don't select it. So we can find out the solution with both the options and then choose the optimal one, here, in this case, select the minimum among all the solutions.

First, we will break the problem into smaller problems. So what are our smaller problems?

The amount is A and coins are v1, v2, ......., vn.

Say MC(j) represents the minimum number of coins required to make a change of amount j.

Smaller Problems:

  1. Select 1st coin (value = v1), Now Smaller problem is the minimum number of coins required to make a change of amount( j-v1), MC(j-v1)
  2. Select 2nd coin (value = v2), Now the Smaller problem is the minimum number of coins required to make a change of amount( j-v2), MC(j-v2)
  3. Likewise up to N
  4. Select nth coin (value = vn), Now the Smaller problem is a minimum number of coins required to make a change of amount( j-v1), MC(j-vn).

We need to find the minimum number of coins required to make a change for j amount. So we will select the minimum of all the smaller problems and add 1 to it because we have selected one coin. Now smaller problems will be solved recursively.

So if we write our recursive equation

MC(j) = Mini=1 to n[MC(j-vi)] +1

NOTE: Before selecting the coin, make sure whether the value of the coin is less than equal to the amount needed.

Using Recursion: Every coin has 2 options, to be selected or not selected so Time Complexity: O(cn) which is very high. (see the code below)

We can reduce the Time Complexity significantly by using Dynamic programming.

Using Bottom-Up Dynamic Programming.

(Click here to read about Bottom-up Dynamic Programming).

  1. We will maintain an array to store the optimal solutions for the smaller problems, say we call it as required[]. length of this array will be amount+1. (starts with 0).
  2. So required[n] will be our final answer, minimum no of coins required to make change for amount 'n'.
  3. Since we are using Bottom-up approach, so will start solving for amounts from 0 to n and save the outcome in the required[] . we will start solving it from the smaller possible amount which is 0 here.
  4. We need 0 coins to make change for amount 0, so required[0]=0.
  5. Now solve for amount = 1, for this the solution would be required[1] = 1 +  required[0]
  6. So for any amount solution would be, try picking each coin one by one (if amount>coin value), and for each picked coin, do remaining = amount - coin value. look for solution for remaining in required[], we must have solved it remaining before since it bottom-up approach. (this is the point where dynamic programming saves computation over recursion). We will do this for each coin, so pick the one which gives the minimum since minimum of all these will the optimal solution for the amount.
  7. Once the solve it for all the amounts from 0 to n, required[n] will be our final answer

Output:

(Dynamic Programming) Minimum Coins required to make change for 20 are: 7

Related Problems: