C++ Coding Test Course, Finding the Minimum Number of Coins

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 N integers 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 coins to store the values of the coins and an array dp to store the number of coins.
  • Use a nested loop to fill the dp array. 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] is INT_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!