14.20 Coin Change

14.20.1 Problem Metadata

14.20.2 Description

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.

14.20.3 Examples

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
Explanation: The amount of 3 cannot be made up with coins of 2.

Example 3:

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

14.20.4 Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

14.20.5 Solution - Dynamic Programming (Unbounded Knapsack)

14.20.5.1 Walkthrough

This problem is a classic Unbounded Knapsack variant where instead of counting combinations (like Coin Change II), we need to find the minimum number of items needed to reach the target amount.

Key Difference from Coin Change II:

Aspect Coin Change (322) Coin Change II (518)
Goal Minimize coin count Count combinations
DP meaning dp[i] = min coins to make amount i dp[i] = number of ways to make amount i
Recurrence dp[i] = min(dp[i], dp[i-coin] + 1) dp[i] += dp[i-coin]
Base case dp[0] = 0 (0 coins for amount 0) dp[0] = 1 (1 way for amount 0)
Initialization dp[i] = ∞ (impossible initially) dp[i] = 0 (no ways initially)
Impossible case Return -1 if dp[amount] == ∞ Return 0 (no ways)

Core DP Strategy:

We use a 1D DP array where dp[i] represents the minimum number of coins needed to make amount i.

Recurrence Relation:

For each coin and each amount i >= coin:

dp[i] = min(dp[i], dp[i - coin] + 1)

This means: - dp[i]: Current minimum coins needed for amount i - dp[i - coin]: Minimum coins for the remaining amount after using one coin - + 1: We’re using one additional coin - min(): Keep the better option (use or don’t use this coin)

Base Case:

dp[0] = 0

We need zero coins to make amount 0.

Initialization:

dp[i] = amount + 1  (or Integer.MAX_VALUE)

Initialize all amounts as “impossible” (requires more coins than could ever be needed). We use amount + 1 because the maximum possible coins needed is amount (using all 1-denomination coins).

Visual Example: coins = [1, 2, 5], amount = 11

Initial State:

dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
      ↑
   amount 0 = 0 coins

Iteration 1: Process coin = 1

For each amount i from 1 to 11, update dp[i] = min(dp[i], dp[i-1] + 1):

i=1:  dp[1] = min(∞, dp[0]+1) = min(∞, 1) = 1
i=2:  dp[2] = min(∞, dp[1]+1) = min(∞, 2) = 2
i=3:  dp[3] = min(∞, dp[2]+1) = min(∞, 3) = 3
...
i=11: dp[11] = min(∞, dp[10]+1) = min(∞, 11) = 11

dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

After processing coin=1: - All amounts 1-11 can be made with 1-coins only - E.g., amount 11 = eleven 1-coins

Iteration 2: Process coin = 2

For each amount i from 2 to 11, update dp[i] = min(dp[i], dp[i-2] + 1):

i=2:  dp[2] = min(2, dp[0]+1) = min(2, 1) = 1  → {2}
i=3:  dp[3] = min(3, dp[1]+1) = min(3, 2) = 2  → {2,1}
i=4:  dp[4] = min(4, dp[2]+1) = min(4, 2) = 2  → {2,2}
i=5:  dp[5] = min(5, dp[3]+1) = min(5, 3) = 3  → {2,2,1}
i=6:  dp[6] = min(6, dp[4]+1) = min(6, 3) = 3  → {2,2,2}
i=7:  dp[7] = min(7, dp[5]+1) = min(7, 4) = 4  → {2,2,2,1}
i=8:  dp[8] = min(8, dp[6]+1) = min(8, 4) = 4  → {2,2,2,2}
i=9:  dp[9] = min(9, dp[7]+1) = min(9, 5) = 5  → {2,2,2,2,1}
i=10: dp[10] = min(10, dp[8]+1) = min(10, 5) = 5  → {2,2,2,2,2}
i=11: dp[11] = min(11, dp[9]+1) = min(11, 6) = 6  → {2,2,2,2,2,1}

dp = [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

Iteration 3: Process coin = 5

For each amount i from 5 to 11, update dp[i] = min(dp[i], dp[i-5] + 1):

i=5:  dp[5] = min(3, dp[0]+1) = min(3, 1) = 1   → {5}
i=6:  dp[6] = min(3, dp[1]+1) = min(3, 2) = 2   → {5,1}
i=7:  dp[7] = min(4, dp[2]+1) = min(4, 2) = 2   → {5,2}
i=8:  dp[8] = min(4, dp[3]+1) = min(4, 3) = 3   → {5,2,1}
i=9:  dp[9] = min(5, dp[4]+1) = min(5, 3) = 3   → {5,2,2}
i=10: dp[10] = min(5, dp[5]+1) = min(5, 2) = 2  → {5,5}
i=11: dp[11] = min(6, dp[6]+1) = min(6, 3) = 3  → {5,5,1}

dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
      ↑                             ↑
   base                          answer

Final Result: dp[11] = 3

The minimum is 3 coins: {5, 5, 1}

Why Loop Order Doesn’t Matter for Minimization:

Unlike Coin Change II (where coins-outer prevents permutation counting), for minimization problems the loop order doesn’t affect correctness:

  • Coins outer (used in solution): Process all amounts for each coin
  • Amounts outer: Process all coins for each amount

Both give the same answer because we’re taking the min() of all possibilities. Order doesn’t matter when optimizing—we consider all combinations anyway.

Counter-example (Why ∞ Initialization is Critical):

If we initialize with 0 instead of ∞:

// WRONG
int[] dp = new int[amount + 1]; // All zeros

Then dp[i] = min(dp[i], dp[i-coin] + 1) would always pick 0, giving incorrect results.

Key Insights:

  1. Minimization vs Counting: Use min() instead of +=
  2. ∞ Initialization: Represents “impossible” state initially
  3. +1 in recurrence: Each coin usage adds 1 to the count
  4. Loop order flexible: Unlike combination counting, order doesn’t matter for optimization
  5. Check final value: If dp[amount] still equals ∞, return -1 (impossible)

14.20.5.2 Analysis

  • Time Complexity: O(n × m)
    • n = amount (inner loop runs from coin to amount)
    • m = coins.length (outer loop processes each coin)
    • For each of the m coins, we update up to n DP states
    • Total operations: O(n × m)
  • Space Complexity: O(n)
    • DP array of size amount + 1
    • No additional data structures needed
    • Space-optimized: Uses 1D array (cannot be further optimized since we need all previous states)

Why 1D Array Works:

Unlike some DP problems that need 2D arrays to avoid overwriting, Coin Change works with 1D because: - We only need values dp[0] through dp[i-1] to compute dp[i] - Processing left-to-right naturally preserves this dependency - The min() operation safely handles updates from the current iteration

14.20.5.3 Implementation Steps

  1. Handle base case:
    • If amount == 0, return 0 immediately (no coins needed)
  2. Initialize DP array:
    • Create dp[amount + 1]
    • Set dp[0] = 0 (base case: zero coins for amount 0)
    • Set all other dp[i] = amount + 1 (represents “impossible” / infinity)
    • Why amount + 1? It’s larger than any valid answer (max coins = amount using all 1-denominations)
  3. Outer loop - Iterate through coins:
    • For each coin in coins[]
    • Order doesn’t matter for minimization (unlike combination counting)
  4. Inner loop - Iterate through amounts:
    • For each amount i from coin to amount (inclusive)
    • Start from coin because we can’t use this coin for amounts smaller than it
    • Update rule: dp[i] = min(dp[i], dp[i - coin] + 1)
      • dp[i]: Current minimum (using previously processed coins)
      • dp[i - coin] + 1: Use one coin + minimum for remaining amount
      • Take minimum because we want the fewest coins
  5. Return result:
    • If dp[amount] > amount, no solution exists → return -1
    • Otherwise, return dp[amount]
    • Why check > amount? If still equals our “impossible” sentinel value

Alternative: Check with exact sentinel

if (dp[amount] == amount + 1) return -1;  // Still impossible

14.20.5.4 Code - Java

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i] = minimum number of coins to make amount i
        int[] dp = new int[amount + 1];

        // Initialize: 0 for base case, impossible (amount+1) for rest
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;  // Represents infinity (impossible)
        }

        // Outer loop: iterate through coins
        for (int coin : coins) {
            // Inner loop: update all amounts that can use this coin
            for (int i = coin; i <= amount; i++) {
                // Take minimum: don't use coin vs use coin
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

        // If still impossible, return -1; otherwise return minimum coins
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

14.20.5.5 Code - Golang

import "math"

func coinChange(coins []int, amount int) int {
    // dp[i] = minimum number of coins to make amount i
    dp := make([]int, amount + 1);

    // Initialize: 0 for base case, impossible (amount+1) for rest
    dp[0] = 0;
    for i := 1; i <= amount; i++ {
        dp[i] = math.MaxInt16  
    }

    // Outer loop: iterate through coins
    for _, coin := range coins {
        // Inner loop: update all amounts that can use this coin
        for i := coin; i <= amount; i++ {
            // Take minimum: don't use coin vs use coin
            dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }

    // If still impossible, return -1; otherwise return minimum coins
    if dp[amount] > amount {
        return -1 
    } else {
        return dp[amount];
    }
}