Minimum Coin Change Problem

Problem statement

If we have an infinite supply of each of C = { $C_{1}$, $C_{2}$, … , $C_{M}$} valued coins and we want to make a change for a given value (N) of cents, what is the minimum number of coins required to make the change?

Example ->
Input: 
coins[] = {25, 10, 5}, N = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents.
Input: 
coins[] = {9, 6, 5, 1}, N = 13
Output: Minimum 3 coins required
We can use one coin of 6 + 6 + 1 cents coins.

Solution: Recursive approach

Start the solution with $sum = N$ cents and in each iteration, find the minimum coins required by dividing the problem into subproblems where we take a coin from {$C_{1}$, $C_{2}$, …, $C_{M}$} and decrease the sum, $N$, by $C[i]$ (depending on the coin we took). Whenever $N$ becomes 0, we have a possible solution. To find the optimal answer, we return the minimum of all answers for which $N$ became 0.

Let’s discuss the recurrence relation now.

• Base case: If N == 0, then 0 coins are required.

• Recursive case: If N > 0 then, the recurrence relation for this problem can be

  minCoins(N , coins[0…m-1]) = min {1 + minCoins(N-coin[i], coins[0…m-1])}, where i varies from 0 to m-1 and coin[i] <= N.

Let’s move on to the implementation now.