In this post, we will discuss how to solve the Coin Change problem using Dynamic Programming in C, C++, and Java.

What is Coin Change Problem?

Given a set of Coins for example coins[] = {1, 2, 3} and total amount as sum, we need to find the number of ways the coins[] can be combined in order to get the sum, abiding the condition that the order of the coins doesn’t matter.

Example:

  • coins[] = {1, 2, 3}
  • sum = 4
  • Possible changes: {1,1,1,1}, {2,2}, {1,3}, {1,1,2}.
  • Solutions: 4

Note: The order of coins does not matter – For example, {1,3} = {3,1}.

The Coin Change Problem can be solved in two ways –

  1. Recursion – Naive Approach, Slow.
  2. Dynamic Programming – Efficient Approach, Fast.

Let’s see the recursive way to solve the coin change problem and study its drawbacks.

Coin Change Problem Solution using Recursion

For every coin, we have two options, either to include the coin or not.

When we include the coin we add its value to the current sum solve(s+coins[i], i) and if not then simply move to next coin in next recursive call solve(s, i++).

Let’s see the code in action.

C

Java

Output

Total solutions: 4

The following picture depicts the recursive calls made in the execution of the program.

coin change recursive solution-min

  • Problems: Time complexity + Overlapping subproblems
  • Exponential time complexity: O(2^n), where n is the number of coins

Clearly, in the recursive method, the algorithm is unnecessarily calculating the same subproblems multiple times. We can use Dynamic Programming to solve the coin change problem in an efficient way.

The dynamic approach to solve the coin change problem is similar to the solution of 01 Knapsack problem using dynamic programming.

Let’s understand how to solve the coin change problem?

Coin Change Problem Solution using Dynamic Programming

We need to use a 2D array (i.e memo table) to store the subproblem’s solution. Refer to the picture below.

coin change problem memoization table

Note:

  • Size of dpTable is (number of coins +1)*(Total Sum +1)
  • First column value is 1 because if total amount is 0, then is one way to make the change (we do not include any coin).

  • Row: Number of coins. The 1st-row index is 0 means no coin is available. 2nd row is 1, it means only 1st coin is available, similarly, the 3rd-row value index is 2 means the first two coins are available to make to the total amount and so on.Row index represent index of coin in coins array not the coin value.
  • Coulmn: Total Amount (sum). The 1st-column index is 0, it means sum value is 0. 2nd column index is 1 therefore combination of coins should make the sum of 1, similarly, 3rd column value is 2, means change of 2 is required and so on.

Thus each table field is storing the solution of subproblems. For Example, dpTable[2][3]=2 means there are 2 ways to get the sum of 3 using the first two coins {1,2}.

The last column and last row value will give the final result.

Here We need to loop through all the indexes (except 1st row and 1st column) in the memo table and make use of previously stored solutions of the subproblems.

  • If coin value is greater than the dpSum, then do not consider the coin i.e dpTable[i][j]=dpTable[i-1][j].
  • If coin value is smaller than the dpSum we can consider the coin i.e dpTable[i][j]=dpTable[i-1][dpSum]+dpTable[i][j-coins[i-1]].

Let’s implement the same in our program.

C

Java

Output

Total Solutions: 4

Overview

  • Time Complexity: O(numberOfCoins*TotalAmount)
  • Space Complexity: O(numberOfCoins*TotalAmount)

IF you have any doubts or suggestion then comment below.

Leave a Reply

Close Menu