Coin Change Program in C++

The coin change problem is a classic algorithmic problem in computer science. Given a set of coins and a target value, the task is to determine the minimum number of coins required to make up the target value. This problem can be solved using dynamic programming.

Syntax

int coinChange(int coins[], int n, int target);

• coins: An array of coin denominations.
• n: The size of the coins array.
• target: The target value to make up using the coins.

Example

#include <iostream>
using namespace std;

int coinChange(int coins[], int n, int target) {
    int dp[target + 1];
    dp[0] = 0;
    for(int i = 1; i <= target; i++) {
        dp[i] = INT_MAX;
    }

    for(int i = 1; i <= target; i {
        for(int j = 0; j < n; j++) {
            if(coins[j] <= i) {
                int sub_res = dp[i - coins[j]];
                if(sub_res != INT_MAX && sub_res + 1 < dp[i]) {
                    dp[i] = sub_res + 1;
                }
            }
        }
    }

    return dp[target];
}

int main() {
    int coins[] = {1, 5, 10, 25};
    int n = sizeof(coins)/sizeof(coins[0]);
    int target = 67;

    cout << "Minimum coins required: " << coinChange(coins, n, target) << endl;

    return 0;
}

Output

Minimum coins required: 4

Explanation

In the above example, we have a set of coins denoted by the coins array. We want to determine the minimum number of coins required to make up a target value of 67. The coinChange function uses dynamic programming to solve the problem. It creates an array called dp of size target + 1 and initializes the first element to 0 and all other elements to infinity. It then uses a double loop to go through every possible combination of coins to make up the target value. For each combination, it calculates the number of coins required and stores it in the dp array. Finally, it returns the minimum number of coins required for the target value.

Use

The coin change problem can be used in a variety of situations, such as making change for a customer in a store or finding the most efficient way to distribute resources. The dynamic programming approach used in the example can be adapted to solve similar problems with variations in the inputs.

Important Points

• The coin change problem involves finding the minimum number of coins required to make up a target value.
• The dynamic programming approach involves creating an array to store the minimum number of coins required for each target value up to the actual target value.
• The time complexity of the algorithm is O(target * n), where n is the size of the coins array and target is the target value.

Summary

The coin change problem is a classic algorithmic problem that can be solved using dynamic programming. The goal is to find the minimum number of coins required to make up a target value using a set of predetermined coin denominations. The dynamic programming approach involves using an array to store the minimum number of coins required for each target value up to the actual target value.