Coin Change

Return minimum amount of coins required to make up to money, we have unlimited coins for each value.

Coin Change

Problem Statement

You are given an array of integers representing coins of different denominations and an integer amount representing a total amount of money.

Your goal is to find the fewest number of coins needed to make up that amount.

• You can assume you have an infinite number of each type of coin.
• If it is impossible to make up the amount using any combination of the given coins, return -1.

Examples

Example 1

• Input: coins = [1, 2, 5], amount = 11
• Output: 3
• Explanation: 11 can be made with three coins: 5 + 5 + 1.

Example 2

• Input: coins = [2], amount = 3
• Output: -1
• Explanation: You cannot make exactly 3 using only 2-denomination coins.

Example 3

• Input: coins = [1], amount = 0
• Output: 0
• Explanation: 0 coins are needed to make an amount of 0.

Memoization (Top-Down Approach)

We evaluate each coin starting from the last index and make a choice: pick the coin or skip it.

• Skip (notTake): We move to the previous coin index and keep the target amount the same.
• Pick (take): We add 1 to our coin count, subtract the coin's value from the target amount, and stay at the same index because we can use the same coin multiple times.
• Base Case: When we reach the very first coin (index = 0), we check if the remaining amount is perfectly divisible by this coin's value. If it is, we return amount / coins[0]. If not, we return a very large number (like 1e9 or Infinity) to indicate it is an invalid path.

var coinChange = function (coins, amount) {
    let dp = Array.from({ length: coins.length }, () => Array(amount + 1));
    
    function recurr(index, value) {
        if (value == 0) {
            return 0;
        }
        
        // Base case: at the first coin, check if the value is divisible
        if (index == 0) {
            if (value % coins[0] === 0) {
                return value / coins[0];
            } else {
                return 1e9; // Represents infinity/invalid path
            }
        }

        if (dp[index][value] !== undefined) {
            return dp[index][value];
        }
        
        let notTake = recurr(index - 1, value);
        let take = Infinity;

        // Only take the coin if its value doesn't exceed the remaining amount
        if (coins[index] <= value) {
            take = 1 + recurr(index, value - coins[index]);
        }

        dp[index][value] = Math.min(take, notTake);
        return dp[index][value];
    }
    
    let ans = recurr(coins.length - 1, amount);

    // If the answer is our infinity placeholder or larger, it's impossible
    if (ans >= 1e9) {
        return -1;
    }

    return ans;
};

Tabulation (Bottom-Up Approach)

Instead of recursion, we can build the answers iteratively using a 2D table where dp[i][value] stores the minimum number of coins needed to make a specific value using a subset of coins up to index i.

• We initialize the first row by checking if each target amount from 0 to amount is divisible by the first coin.
• For the remaining rows, we build upon the previously computed minimums, choosing the minimum between skipping the current coin (notTake) and taking it (take).

var coinChange = function (coins, amount) {
    let dp = Array.from({ length: coins.length }, () => Array(amount + 1).fill(0));

    // A target of 0 always requires 0 coins
    for (let i = 0; i < coins.length; i++) {
        dp[i][0] = 0;
    }
    
    // Fill the base case row for the very first coin
    for (let target = 0; target <= amount; target++) {
        if (target % coins[0] === 0) {
            dp[0][target] = target / coins[0];
        } else {
            dp[0][target] = 1e9;
        }
    }

    // Fill the rest of the DP table
    for (let i = 1; i < coins.length; i++) {
        for (let value = 0; value <= amount; value++) {
            
            let notTake = dp[i - 1][value];
            let take = Infinity;

            if (coins[i] <= value) {
                // Add 1 to the coin count and look up the remaining value in the same row
                take = 1 + dp[i][value - coins[i]];
            }

            dp[i][value] = Math.min(take, notTake);
        }
    }
    
    // If the final cell contains our infinity placeholder, no combination was found
    if (dp[coins.length - 1][amount] >= 1e9) {
        return -1;
    }

    return dp[coins.length - 1][amount];
};