Picture this, you are given an array of coins with varying denominations and an integer sum representing the total amount of money. You must return the fewest coins required to make up that sum; if that sum cannot be constructed, return -1. There are two solutions to the coin change problem: the first is a naive solution, a recursive solution of the coin change program, and the second is a dynamic solution, which is an efficient solution for the coin change problem. The time complexity of the coin change problem is (in any case) (n*c), and the space complexity is (n*c) (n).
What Is Dynamic Programming?
- Dynamic Programming or DP is an algorithmic technique for solving optimization problems by breaking them down into simpler subproblems and exploiting the fact that the optimal solution to the overall situation is dependent on the optimal solution to its subproblems and taking advantage of the fact that the optimal solution to the overall situation is dependent on the optimal solution to its subproblems.
- Dynamic Programming is a programming procedure that combines the precision of a complete search with the efficiency of greedy algorithms.
- The main limitation of dynamic programming is that it can only be applied to problems divided into sub-problems. Furthermore, each of the sub-problems should be solvable on its own.
- The concept of sub-problems is that these sub-problems can be used to solve a more significant problem. As a result, dynamic programming algorithms are highly optimized.
- The goal of greedy algorithms is usually local optimization. The dynamic programming approach, on the other hand, attempts to optimize the problem as a whole.
Now that you have grasped the concept of dynamic programming, look at the coin change problem.
Introduction to Coin Change Problem
You are given an array of coins with varying denominations and an integer sum representing the total amount of money; you must return the fewest coins required to make up that sum; if that sum cannot be constructed, return -1.
Now, take a look at what the coin change problem is all about.
You are given a sequence of coins of various denominations as part of the coin change problem. For example, consider the following array a collection of coins, with each element representing a different denomination.
|
{ 2, 3, 5, 10, 20, 30, 50 }; |
Our goal is to use these coins to accumulate a certain amount of money while using the fewest (or optimal) coins. Furthermore, you can assume that a given denomination has an infinite number of coins. To put it another way, you can use a specific denomination as many times as you want.
For example, if you want to reach 78 using the above denominations, you will need the four coins listed below.
{ 3, 5, 20, 50 };
Consider the following another set of denominations:
|
{ 2, 3, 5, 6 }; |
If you want to make a total of 9, you only need two coins in these denominations, as shown below:
|
{ 3, 6 }; |
However, if you recall the greedy algorithm approach, you end up with three coins for the above denominations (5, 2, 2). This is due to the greedy algorithm's preference for local optimization.
After understanding a coin change problem, you will look at the pseudocode of the coin change problem in this tutorial.
Pseudocode of Coin Change Problem
The Coin Change Problem pseudocode is as follows:
- Initialize a new array for dynamicprog of length n+1, where n is the number of different coin changes you want to find.
- Because there is only one way to give change for 0 dollars, set dynamicprog[0] to 1.
- Iterate through the array for each coin change available and add the value of dynamicprog[index-coins[i]] to dynamicprog[index] for indexes ranging from '1' to 'n'.
- dynamicprog[n] return value
After understanding the pseudocode coin change problem, you will look at Recursive and Dynamic Programming Solutions for Coin Change Problems in this tutorial.
Solutions of Coin Change Problem
There are two solutions to the Coin Change Problem –
Recursion - Naive and slow approach.
Dynamic Programming – A timely and efficient approach
Now, look at the recursive method for solving the coin change problem and consider its drawbacks.
Coin Change Problem Solution Using Recursion
You have two options for each coin: include it or exclude it.
- coins[] = {1, 2, 3}
- sum = 4
When you include a coin, you add its value to the current sum solution(sol+coins[i], I, and if it is not equal, you move to the next coin, i.e., the next recursive call solution(sol, i++).
Total solutions are 4.
The diagram below depicts the recursive calls made during program execution.
The recursive method causes the algorithm to calculate the same subproblems multiple times. Therefore, to solve the coin change problem efficiently, you can employ Dynamic Programming.
Coin Change Problem Solution Using Dynamic Programming
The dynamic approach to solving the coin change problem is similar to the dynamic method used to solve the 01 Knapsack problem.
To store the solution to the subproblem, you must use a 2D array (i.e. table). Then, take a look at the image below.
- The size of the dynamicprogTable is equal to (number of coins +1)*(Sum +1).
- The first column value is one because there is only one way to change if the total amount is 0. (we do not include any coin).
- Row: The total number of coins. The fact that the first-row index is 0 indicates that no coin is available. If the value index in the second row is 1, only the first coin is available. Similarly, if the value index in the third row is 2, it means that the first two coins are available to add to the total amount, and so on. The row index represents the index of the coin in the coins array, not the coin value.
- Column: Total amount (sum). Because the first-column index is 0, the sum value is 0. The second column index is 1, so the sum of the coins should be 1. Similarly, the third column value is 2, so a change of 2 is required, and so on.
As a result, each table field stores the solution to a subproblem. For example, dynamicprogTable[2][3]=2 indicates two ways to compute the sum of three using the first two coins 1,2.
The final outcome will be calculated by the values in the last column and row.
In this case, you must loop through all of the indexes in the memo table (except the first row and column) and use previously-stored solutions to the subproblems.
- If the coin value is greater than the dynamicprogSum, the coin is ignored, i.e. dynamicprogTable[i][j]=dynamicprogTable[i-1][j].
- If the coin value is less than the dynamicprogSum, you can consider it, i.e. dynamicprogTable[i][j]=dynamicprogTable[i-1].[dynamicprogSum]+dynamicprogTable[i][j-coins[i-1]].
You will look at the complexity of the coin change problem after figuring out how to solve it.
The Complexity of Coin Change Problem
- The complexity of solving the coin change problem using recursive time and space will be:
Problems: Overlapping subproblems + Time complexity
O(2n) is the time complexity, where n is the number of coins
- Time and space complexity will be reduced by using dynamic programming to solve the coin change problem:
O(numberOfCoins*TotalAmount) time complexity
O(numberOfCoins*TotalAmount) is the space complexity.
You will now see a practical demonstration of the coin change problem in the C programming language.
Code Implementation of Coin Change Problem
1. Recursive solution code for the coin change problem
|
#include <stdio.h> int coins[] = {1,2,3}; int numberofCoins = 3, sum = 4; int solution(int sol, int i){ if(numberofCoins == 0 || sol > sum || i>=numberofCoins) return 0; else if(sol == sum) return 1; return solution(sol+coins[i],i) + solution(sol,i+1) ; } int main() { printf("Total solutions: %d",solution(0,0)); return 0; } |
Output:
2. Dynamic Programming solution code for the coin change problem
|
#include <stdio.h> int coins[] = {1,2,3}, sum=4; int numberofCoins = 3; //Function to initialize 1st column of dynamicprogTable with 1 void initdynamicprogTable(int dynamicprogTable[][5]) { int i; //First row to 0 for(i=1; i<=sum+1; i++){ dynamicprogTable[0][i] = 0; } //First column to 1 for(i=1; i<=numberofCoins; i++){ dynamicprogTable[i][0] = 1; } } int solution(int dynamicprogTable[][5]){ int coinindex, dynamicprogSum; for(coinindex=1; coinindex<numberofCoins+1; coinindex++){ for(dynamicprogSum=1; dynamicprogSum< 5; dynamicprogSum++){ //value of coin should be less than or equal to sum value to consider it if(coins[coinindex-1] > dynamicprogSum) dynamicprogTable[coinindex][dynamicprogSum] = dynamicprogTable[coinindex-1][dynamicprogSum]; else dynamicprogTable[coinindex][dynamicprogSum] = dynamicprogTable[coinindex-1][dynamicprogSum]+dynamicprogTable[coinindex][dynamicprogSum-coins[coinindex-1]]; } } //return final row and column value return dynamicprogTable[numberofCoins][sum]; } int main() { int dynamicprogTable[numberofCoins+1][5]; initdynamicprogTable(dynamicprogTable); printf("Total Solutions: %d",solution(dynamicprogTable)); return 0; } |
Output:
Following the implementation of the coin change problem code, you will now look at some coin change problem applications.
Applications of Coin Change Problem
This algorithm can be used to distribute change, for example, in a soda vending machine that accepts bills and coins and dispenses coins.
Buying a 60-cent soda pop with a dollar is one example. This leaves 40 cents to change, or in the United States, one quarter, one dime, and one nickel for the smallest coin pay. However, if the nickel tube were empty, the machine would dispense four dimes.
Last but not least, in this coin change problem article, you will summarise all of the topics that you have explored thus far.
Next Steps
In the coin change problem, you first learned what dynamic programming is, then you knew what the coin change problem is, after that, you learned the coin change problem's pseudocode, and finally, you explored coin change problem solutions. After that, you learned about the complexity of the coin change problem and some applications of the coin change problem. Finally, you saw how to implement the coin change problem in both recursive and dynamic programming.
Suppose you want more that goes beyond Mobile and Software Development and covers the most in-demand programming languages and skills today. In that case, Simplilearn's Full Stack Development course is a good fit.
Do you have any questions about this Coin Change Problem tutorial? If you do, please leave them in the comments section at the bottom of this page. Our experts will be happy to respond to your questions as earliest as possible!
