Approach-1
A recursive method is used in this approach.
- We start with N and divide the problem into smaller subproblems with each iteration.
- This is accomplished by subtracting N from each coin in the coins array.
- The scenario in which N equals 0 provides the desired solution.
- We return the smallest of all possible combinations as an ideal solution.
C++ Code
#include <bits/stdc++.h>
using namespace std;
// initializing coins array
int coins[] = { 10, 25, 5 };
// array for memoization technique
int dp[1000] = { 0 };
// Here, N is sum and M is total_coins
int minCoins(int N, int M)
{
for (int i = 0; i <= N; i++)
{
// Initializing all dp[] value to INT_MAX
dp[i] = INT_MAX;
}
// Base case if sum = zero means rupees = 0
dp[0] = 0;
// outer loop denotes possible values of sum between 1 to N
for (int i = 1; i <= N; i++) {
//Inner loop denotes index of coin array.
for (int j = 0; j < M; j++) {
if (coins[j] <= i) {
//Solution might have the newly added coin
dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
}
}
}
return dp[N];
}
int main()
{
int sum = 30;
int total_coins = 3;
cout << "Minimum number of coins needed are " << minCoins(sum, total_coins);
}
You can also try this code with Online C++ Compiler
Run Code
Output
Minimum number of coins needed are 2
You can also try this code with Online C++ Compiler
Run Code
Complexity Analysis
- Time Complexity: O(2^N)
- Space Complexity: O(2^N)
Note: The above approach does not work efficiently for more large inputs. Therefore, The recursive technique fails in this example.
Try and compile by yourself with the help of online C++ Compiler for better understanding.
Check out Longest Common Substring
Approach-2
This method is based on the concept of bottom-up dynamic programming.
- There is a condition of overlapping subproblems because subproblems are computed repeatedly.
- The problem of recomputation can be overcome by applying the memoization property, that is, by creating a dp[] array that keeps the computed values at a specific stage.
- Calculate all potential combinations at each level.
- The last value in the dp[] array provides the answer after all the combinations.
C++ Code
#include <bits/stdc++.h>
using namespace std;
// initializing the coins array
int coins[] = { 10, 25, 5 };
// array for memoization
int dp[1000] = { 0 };
int minCoins(int N, int M) // N = sum and M = total coins
{
for (int i = 0; i <= N; i++)
dp[i] = INT_MAX; // Initialising all dp[] elements to INT_MAX
dp[0] = 0; // Base case if sum = 0
//Iterating in outer loop for all the possible sum values
for (int i = 1; i <= N; i++) {
//Inner loop denotes the index of coin array.
for (int j = 0; j < M; j++) {
if (coins[j] <= i) {
//Solution might include the newly added coins
dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
}
}
}
return dp[N];
}
int main()
{
int sum = 30;
int total_coins = 3;
cout << "Minimum coins needed are " << minCoins(sum, total_coins);
}
You can also try this code with Online C++ Compiler
Run Code
Output
Minimum coins needed are 2
You can also try this code with Online C++ Compiler
Run Code
Complexity Analysis
- Time Complexity: The time complexity of the above code is O(total_coins * sum) ≈ O(N2). Since the outcomes from each step are saved and reused in subsequent cycles, this is a far more efficient technique.
-
Space Complexity: The space complexity for the above code will be O(N2) due to the auxiliary space used in the program.
Since the outcomes from each step are saved and reused in subsequent cycles, this is a far more efficient technique.
Check out this problem - Minimum Coin Change Problem
Must Read Julia Programming Language
FAQs
-
What is bottom-up dynamic programming?
The bottom-up technique (to dynamic programming) evaluates the “smaller” subproblems first, then solves the bigger subproblems using the solutions to the smaller ones.
-
What do you mean by memoization in dynamic programming?
Memoization is a recursive algorithm performance improvement method. It involves changing the recursive algorithm to store answers to problems in an array as they are discovered. Instead of needing to recalculate results, recursive calls may search them up in the array. Since partial results are never computed twice, memorization boosts performance, for example, the Fibonacci series.
Key Takeaways
This article extensively discussed the Coin Change Problem in C++. The article explains the different approaches used to solve the problem. There are many more approaches, but these are the most efficient in terms of time and space.
Recommended Readings:
We hope that this blog has helped you enhance your knowledge regarding dynamic programming and recursion using this article and if you would like to learn more, check out our articles on Coding Ninjas. Do upvote our blog to help other ninjas grow.
Happy Coding!