Coin Change

Concept

LeetCode #322.
Problem: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

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

As we learned in the Greedy section, a Greedy algorithm (always picking the biggest coin) completely fails if the denominations are weird ([25, 20, 5, 1], amount 40). To mathematically guarantee the absolute fewest coins, we must use Dynamic Programming.

The DP Strategy

We want to find the minimum coins for amount = 11.
What if we knew the absolute minimum coins required to make 10 cents? Or 9 cents? Or 6 cents?

If we are trying to make 11 cents, and we have a 1-cent coin, a 2-cent coin, and a 5-cent coin, our last step MUST be one of three choices:

1. We had 10 cents, and we added a 1-cent coin. (Total coins: dp[10] + 1).
2. We had 9 cents, and we added a 2-cent coin. (Total coins: dp[9] + 1).
3. We had 6 cents, and we added a 5-cent coin. (Total coins: dp[6] + 1).

To find the absolute minimum for 11, we just take the Math.min() of those three possibilities!

Recurrence Relation:
dp[i] = Math.min(dp[i - coin1] + 1, dp[i - coin2] + 1, ...)

Implementation (Tabulation)

We create a dp array where the index represents the amount. The array will go from 0 all the way up to 11. We initialize it with Infinity (because we are looking for a minimum).

// Time Complexity: O(A * C) (Amount * Number of Coins)
// Space Complexity: O(A) (The DP Array)

function coinChange(coins: number[], amount: number): number {
    // 1. Create the DP table, initializing with Infinity
    // The table size is amount + 1 because we need an index for 0
    const dp = new Array(amount + 1).fill(Infinity);
    
    // 2. Base Case: It takes 0 coins to make 0 cents!
    dp[0] = 0;

    // 3. Build the table from 1 cent up to the target amount
    for (let currentAmount = 1; currentAmount <= amount; currentAmount++) {
        
        // At each amount, try every single coin we have
        for (const coin of coins) {
            
            // Can we even use this coin? (Is the coin smaller than our target amount?)
            if (currentAmount - coin >= 0) {
                // The Recurrence Relation
                dp[currentAmount] = Math.min(
                    dp[currentAmount],             // Leave it as is
                    dp[currentAmount - coin] + 1   // Try using this coin! (+1 coin used)
                );
            }
        }
    }

    // 4. If the final amount is still Infinity, it was impossible to make!
    return dp[amount] === Infinity ? -1 : dp[amount];
}

Coin Change II (Total Combinations)

LeetCode #518. What if the problem changes from “Fewest number of coins” to “Total number of combinations that make up that amount”?

The logic flips from Math.min to Addition!
If I can make 6 cents in 4 different ways, and I have a 5-cent coin, that adds exactly 4 new ways to make 11 cents.

Recurrence Relation:
dp[i] = dp[i] + dp[i - coin]

function change(amount: number, coins: number[]): number {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1; // There is exactly 1 way to make 0 cents (use no coins)

    // Notice the loops are SWAPPED compared to Coin Change I!
    for (const coin of coins) {
        for (let currentAmount = coin; currentAmount <= amount; currentAmount++) {
            dp[currentAmount] += dp[currentAmount - coin];
        }
    }

    return dp[amount];
}

Interview Questions

Q: In Coin Change II, why did you swap the order of the for loops (looping Coins first, then Amount)?
A: This is a brilliant nuance. If you loop Amount first, then Coins, you will count permutations (1+2 and 2+1 will be counted as two separate ways to make 3). By looping Coins first, you process all the 1s, then all the 2s. This physically forces the combinations to be generated in strict sorted order, perfectly deduplicating the permutations so 1+2 is the only counted valid combination!

Q: Can you do State Reduction ($O(1)$ space) on Coin Change I?
A: No. State reduction only works if the look-back distance is a small, fixed constant (like dp[i-1]). Because the coins could be anything ([1, 50, 1000]), dp[i] might need to jump back 1000 indices to check dp[i-1000]. You must keep the entire array in memory.