Hello! Today we will discuss one of the frequently asked questions in C++ coding tests, which is ‘Finding the Minimum Number of Coins.’ This problem is a basic algorithm problem that determines the minimum number of coins needed to make a given amount. We will analyze this problem step by step and solve it through implementation.
Problem Description
Given the types of coins and a target amount, find out the minimum number of coins required to make that amount. Each coin is assumed to be available in infinite supply.
Input Format
- The first line contains the number of coin types
N(1 ≤ N ≤ 100). - The second line contains
Nintegers representing the value of each coin. - The third line contains the target amount
M(1 ≤ M ≤ 10,000).
Output Format
- Output the minimum number of coins needed to make the target amount. If it is not possible to make the target amount, output
-1.
Example
Example Input: 3 1 3 4 6 Example Output: 2
In the above example, there are 3 types of coins with values of 1, 3, and 4. To make the target amount of 6, using the coins 3 and 3 will result in a total of 2 coins.
Approach to Solve the Problem
This problem can be solved using Dynamic Programming or Greedy Algorithm. However, when there are multiple types of coins, using Dynamic Programming provides a more general solution. Below is the approach to solving the problem using Dynamic Programming.
Basic Concept of Dynamic Programming
Dynamic Programming (DP) is a method of solving large problems by dividing them into smaller ones. In this problem, we can reduce redundant calculations while finding the minimum number of coins required to make each amount to reach the target amount. We will use a DP array to store the minimum number of coins needed for each amount.
Definition of DP Array
We define dp[i] as the minimum number of coins needed to make the target amount i. We set the initial value dp[0] = 0 and initialize the other amounts to INT_MAX (infinity).
Solution
Now, let’s implement this based on the theory. The code is as follows:
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int N, M;
cin >> N; // Input the number of coin types
vector coins(N);
for (int i = 0; i < N; ++i) {
cin >> coins[i]; // Input the value of each coin
}
cin >> M; // Input the target amount
vector dp(M + 1, INT_MAX); // Initialize DP array
dp[0] = 0; // The number of coins needed to make 0 amount is 0
// Fill the DP array
for (int i = 1; i <= M; ++i) {
for (int j = 0; j < N; ++j) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
// Output the result
if (dp[M] == INT_MAX) {
cout << -1 << endl; // If it cannot be made
} else {
cout << dp[M] << endl; // Output the minimum number of coins
}
return 0;
}
Code Explanation
- First, include the necessary libraries and input the number of coin types and the target amount.
- Define a vector
coinsto store the values of the coins and an arraydpto store the number of coins. - Use a nested loop to fill the
dparray. The outer loop iterates over the target amount, and the inner loop iterates over the types of coins to calculate the minimum number of coins. - In the end, if the value of
dp[M]isINT_MAX, it means the amount M cannot be made, so output-1. Otherwise, output the minimum number of coins.
Complexity Analysis
The time complexity of this algorithm is O(N*M). Here, N is the number of coin types, and M is the target amount. The space complexity is O(M), which is the space needed to maintain the DP array.
Conclusion
In this lecture, we learned how to solve the ‘Finding the Minimum Number of Coins’ problem frequently occurring in C++ coding tests using Dynamic Programming. I hope this problem helped you understand the basic concepts of Dynamic Programming and how to use the DP array to solve problems. Dynamic Programming is an essential technique for solving various problems, so practice adequately to improve your understanding! I encourage you to also work on other algorithm problems to enhance your skills.
Thank you!