322. Coin Change – Leetcode Solutions

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Step 1: Create a dp array of size amount + 1 initialized to a large value (amount + 1)
        # amount + 1 is used as a large value, representing "infinity" because we can't have
        # more than 'amount' coins to make up 'amount'.
        dp = [amount + 1] * (amount + 1)
        
        # Step 2: Base case: 0 coins are needed to make the amount 0
        dp[0] = 0
        
        # Step 3: Iterate through each amount from 1 to amount
        for i in range(1, amount + 1):
            # Step 4: Check each coin in coins to find the minimum number of coins required
            for coin in coins:
                if i - coin >= 0:  # If it's valid to use the current coin
                    # Update dp[i] to the minimum of the current dp[i] and dp[i - coin] + 1
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        # Step 5: Check if it's possible to form the given amount with the coins provided
        return dp[amount] if dp[amount] != amount + 1 else -1

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // Step 1: Create a DP table to store the minimum coins for each amount from 0 to 'amount'.
        // Initialize dp[0] = 0, since no coins are needed to make the amount 0.
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;

        // Step 2: Iterate over each amount from 1 to 'amount'.
        for (int i = 1; i <= amount; ++i) {
            // Step 3: For each coin in the list of coins, try to reduce the problem.
            for (int coin : coins) {
                // If the current coin can be used (i.e., i >= coin), we can attempt to use it.
                if (i - coin >= 0 && dp[i - coin] != INT_MAX) {
                    // Update dp[i] with the minimum coins required to make amount 'i'.
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // Step 4: If dp[amount] is still INT_MAX, it means it's not possible to make the amount.
        // Return -1 in that case; otherwise, return dp[amount] which has the minimum coins needed.
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

var coinChange = function(coins, amount) {
    // Step 1: Create an array to store the minimum number of coins needed for each amount from 0 to 'amount'.
    // Initialize it with a large value (amount + 1 is a good choice because it's larger than any possible result).
    let dp = new Array(amount + 1).fill(amount + 1);
    
    // Step 2: Base case - To make the amount of 0, 0 coins are needed.
    dp[0] = 0;

    // Step 3: Loop over each amount from 1 to the target 'amount'
    for (let i = 1; i <= amount; i++) {
        // Step 4: For each coin in the 'coins' array, check if we can use this coin to make the current amount 'i'.
        for (let coin of coins) {
            if (i - coin >= 0) { // If the coin can be used (i.e., the remaining amount is non-negative)
                // Step 5: Update the dp array. The new value for dp[i] will be the minimum of:
                // the current value of dp[i] OR dp[i - coin] + 1 (which means using one coin of denomination 'coin')
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // Step 6: After processing all amounts, check if the amount can be made up with the given coins.
    // If dp[amount] is still larger than 'amount', return -1 (it's not possible to make that amount).
    return dp[amount] > amount ? -1 : dp[amount];
};

class Solution {
    public int coinChange(int[] coins, int amount) {
        // If the amount is 0, no coins are needed, so return 0
        if (amount == 0) return 0;

        // Create a DP array to store the minimum coins required for each amount
        // dp[i] will store the fewest number of coins required to make up the amount 'i'
        int[] dp = new int[amount + 1];

        // Initialize the DP array with a large number (greater than any possible coin count)
        // We choose amount + 1, since this is a safe upper bound
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
        }

        // Base case: 0 amount requires 0 coins
        dp[0] = 0;

        // Iterate over each amount from 1 to 'amount'
        for (int i = 1; i <= amount; i++) {
            // For each coin, try to see if it can contribute to the current amount 'i'
            for (int coin : coins) {
                // If the coin value is less than or equal to the current amount 'i'
                if (coin <= i) {
                    // Update the dp value by considering the current coin
                    // Take the minimum between the current value and (dp[i - coin] + 1)
                    // dp[i - coin] represents the fewest number of coins required to make amount (i - coin)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // After filling the DP table, if dp[amount] still holds the initial large value,
        // it means it's impossible to make that amount with the given coins, so return -1.
        // Otherwise, return the value of dp[amount], which is the fewest coins needed.
        return dp[amount] > amount ? -1 : dp[amount];
    }
}