Coin Change Problem

The Coin Change Problem is a classic algorithmic problem frequently encountered in computer science.

Given a set of coin denominations and a target amount, the task is to find the minimum number of coins required to make up that amount.

pseudocode:

function coinChange(coins, amount):
    // Create an array to store the minimum number of coins required for each amount from 0 to 'amount'
    dp = new Array(amount + 1)
    dp[0] = 0 // Base case: 0 coins are required to make amount 0
    
    // Initialize all other values in dp array to infinity
    for i from 1 to amount:
        dp[i] = ∞
    
    // Iterate through each coin
    for coin in coins:
        // For each coin, update dp array from the current coin value to the amount
        for i from coin to amount:
            // Update dp[i] if using current coin reduces the number of coins needed for amount i
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    // If dp[amount] is still infinity, it means no combination of coins can make the amount
    if dp[amount] is ∞:
        return -1
    else:
        return dp[amount]

function minCoins(coins, amount) {
    // Create an array to store the minimum number of coins required for each amount from 0 to amount
    let dp = new Array(amount + 1).fill(Infinity);
    
    // Base case: 0 coins required to make 0 amount
    dp[0] = 0;

    // Iterate through all amounts from 1 to the target amount
    for (let i = 1; i <= amount; i++) {
        // Iterate through all coin denominations
        for (let j = 0; j < coins.length; j++) {
            // Check if the current coin denomination can be used to make up the current amount
            if (coins[j] <= i) {
                // Update the minimum number of coins required for the current amount
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }

    // If dp[amount] is still Infinity, it means the amount cannot be made up with the given coins
    if (dp[amount] === Infinity) {
        return -1; // Return -1 to indicate impossibility
    } else {
        return dp[amount]; // Otherwise, return the minimum number of coins required
    }
}

// Example usage:
const coins = [1, 2, 5];
const amount = 11;
console.log("Minimum number of coins required:", minCoins(coins, amount)); // Output: 3 (using 5, 5, and 1 coins)

In this implementation, we use dynamic programming to build up the solution incrementally.

We initialize an array dp to store the minimum number of coins required for each amount from 0 to the target amount.

We then iterate through all amounts from 1 to the target amount, and for each amount, we iterate through all coin denominations.

If the current coin denomination can be used to make up the current amount, we update the dp array with the minimum number of coins required.

Finally, we return dp[amount] as the result. If dp[amount] is still Infinity, it means the amount cannot be made up with the given coins, so we return -1 to indicate impossibility.