Introduction:
In the realm of dynamic programming, the Minimum Coin Change Problem holds significant importance. It presents a fascinating challenge of determining the minimum number of coins required to make change for a given value using a set of coin denominations. In this article, we will delve into this problem, understand its intricacies, and explore an efficient solution using dynamic programming.✌
You are given an amount denoted by value. You are also given an array of coins. The array contains the denominations of the given coins. You need to find the minimum number of coins to make the change for value using the coins of given denominations. Also, keep in mind that you have infinite supply of the coins.
Problem Statement:
Given a target value and an array of coin denominations, the objective is to find the minimum number of coins needed to make exact change for the given value using the provided coins. It is important to note that we have an infinite supply of coins for each denomination.
Example Scenarios:
Input: value = 5, numberOfCoins = 3, coins[] = {3, 6, 3} Output: Not Possible Explanation: It is impossible to make exact change for 5 using the given coin denominations {3, 6, 3}.
Input: value = 10, numberOfCoins = 4, coins[] = {2, 5, 3, 6} Output: 2 Explanation: We can use two 5 coins to make 10. Thus, the minimum number of coins required is 2.
Code:
//{ Driver Code Starts
//Initial Template for C++
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//Complete this function
class Solution
{
public:
// Function to find the minimum number of coins to make the change
// for value using the coins of given denominations.
long long minimumNumberOfCoins(int coins[], int numberOfCoins, int value)
{
long long dp[numberOfCoins + 1][value + 1];
for (long long i = 0; i <= numberOfCoins; i++)
dp[i][0] = 0;
for (long long j = 1; j <= value; j++)
dp[0][j] = INT_MAX - 1;
for (long long i = 1; i <= numberOfCoins; i++)
{
for (long long j = 1; j <= value; j++)
{
dp[i][j] = dp[i - 1][j];
if (coins[i - 1] <= j)
dp[i][j] = min(dp[i][j], 1 + dp[i][j - coins[i - 1]]);
}
}
return dp[numberOfCoins][value] != INT_MAX - 1 ? dp[numberOfCoins][value] : -1;
}
};
//{ Driver Code Starts.
int main() {
//taking total count of testcases
int testcases;
cin>>testcases;
while(testcases--)
{
//taking value
int value;
cin>>value;
//taking number of coins
int numberOfCoins;
cin>>numberOfCoins;
int coins[numberOfCoins];
//taking value of each coin
for(int i=0;i<numberOfCoins;i++)
cin>>coins[i];
Solution obj;
//calling function minimumNumberOfCoins()
int answer=obj.minimumNumberOfCoins(coins,numberOfCoins,value);
//printing "Not Possible" if answer is -1
//else printing answer
if(answer==-1)
cout<<"Not Possible"<<endl;
else
cout<<answer<<endl;
}
return 0;
}
// }
Explaination
Certainly! Let's go through the code step by step to understand how it finds the minimum number of coins to make change for a given value using the provided denominations.
1. The code defines a class named `Solution` and a member function `minimumNumberOfCoins` that takes three parameters: an array of coins (`coins[]`), the number of coins (`numberOfCoins`), and the target value (`value`).
2. It declares a 2D array `dp` of size `(numberOfCoins + 1) x (value + 1)` to store the intermediate results. The rows represent the coins, and the columns represent the values from 0 to the target value.
3. The next step is to initialize the `dp` array. The loop `for (long long i = 0; i <= numberOfCoins; i++)` initializes the first column of the `dp` array to 0, which means that we don't need any coins to make a change for a value of 0.
4. The loop `for (long long j = 1; j <= value; j++)` initializes the first row of the `dp` array to `INT_MAX - 1`. This value is used as a placeholder to represent an impossible scenario. By setting it to a large value, we ensure that it doesn't cause overflow when we add 1 to it later.
5. The nested loops `for (long long i = 1; i <= numberOfCoins; i++)` and `for (long long j = 1; j <= value; j++)` fill in the `dp` array with the minimum number of coins required to make change for each value.
6. Inside the inner loop, `dp[i][j] = dp[i - 1][j];` sets the current value to the minimum number of coins required to make change without using the current coin (`coins[i-1]`).
7. The condition `if (coins[i - 1] <= j)` checks if the current coin can be used to make change for the current value. If so, we update `dp[i][j]` to either keep the current minimum number of coins or consider using the current coin and add 1 to the minimum number of coins required to make change for `j - coins[i-1]` value.
8. Finally, the function returns `dp[numberOfCoins][value]` if it is not equal to `INT_MAX - 1`. If it is equal to `INT_MAX - 1`, it means it is not possible to make change for the given value using the provided coins, so the function returns -1.
Conclusion:
The Minimum Coin Change Problem poses an intriguing challenge in dynamic programming. By utilizing the concept of dynamic programming and filling in a 2D array iteratively, we can efficiently find the minimum number of coins required to make change for a given value. This problem showcases the power and versatility of dynamic programming as a problem-solving technique.
Click here - Binary-String-Problem for learning similar problems.
