Coin Change Problem: Minimum Coins DP Solution

Key Insights

• The greedy approach fails for coin change because locally optimal choices don’t guarantee globally optimal solutions—coins [1, 3, 4] with amount 6 proves this definitively.
• The recurrence relation dp[amount] = min(dp[amount - coin] + 1) captures the core insight: the minimum coins for any amount equals one plus the minimum coins for the remaining amount after using each valid coin.
• Bottom-up tabulation eliminates recursion overhead and makes the solution’s O(amount × coins) time complexity explicit while using only O(amount) space.

Problem Definition & Real-World Context

The coin change problem asks a deceptively simple question: given a set of coin denominations and a target amount, what’s the minimum number of coins needed to make exact change?

Formally: given an array coins of distinct positive integers representing coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. If it’s impossible, return -1.

This problem appears everywhere in real systems. Vending machines need to dispense minimal change. Payment processors optimize transaction fees. Currency exchange systems minimize physical currency handling. Even video game economies use these algorithms for in-game currency management.

The intuitive approach—always pick the largest coin that fits—seems reasonable. It works for US currency denominations [1, 5, 10, 25]. But consider coins [1, 3, 4] with target amount 6:

• Greedy picks 4, then 1, then 1 = 3 coins
• Optimal picks 3 and 3 = 2 coins

The greedy approach fails because locally optimal choices don’t compose into globally optimal solutions. This is precisely why we need dynamic programming.

Brute Force Approach & Its Limitations

The naive solution explores every possible combination of coins recursively. For each coin, we either use it (and recurse with the reduced amount) or skip it:

def min_coins_brute(coins: list[int], amount: int) -> int:
    def helper(remaining: int) -> int:
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        
        min_count = float('inf')
        for coin in coins:
            result = helper(remaining - coin)
            if result != float('inf'):
                min_count = min(min_count, result + 1)
        
        return min_count
    
    result = helper(amount)
    return result if result != float('inf') else -1

# Trace for coins=[1,2,5], amount=5:
# helper(5) calls helper(4), helper(3), helper(0)
# helper(4) calls helper(3), helper(2), helper(-1)
# helper(3) calls helper(2), helper(1), helper(-2)
# ... massive redundancy

The problem is exponential time complexity. Each call branches into len(coins) subcalls, creating a tree of depth amount. The time complexity is O(coins^amount)—completely impractical for real inputs.

Worse, we’re solving the same subproblems repeatedly. helper(3) gets called from helper(4), helper(5), and many other paths. This redundancy screams for memoization.

Identifying the DP Substructure

Two properties make a problem suitable for dynamic programming:

Optimal Substructure: The optimal solution contains optimal solutions to subproblems. If the minimum coins for amount 11 uses a coin of value 5, then the remaining coins must be the minimum solution for amount 6. You can’t improve the overall solution by using a suboptimal solution for the subproblem.

Overlapping Subproblems: The same subproblems appear multiple times. Computing min_coins(6) requires min_coins(5), min_coins(4), and min_coins(1). Computing min_coins(7) also requires some of these same values.

The recurrence relation captures this structure:

dp[0] = 0  (base case: zero coins for zero amount)
dp[amount] = min(dp[amount - coin] + 1) for each coin where coin <= amount
dp[amount] = infinity if no coin fits

Here’s the top-down memoized solution:

def min_coins_memo(coins: list[int], amount: int) -> int:
    memo = {}
    
    def helper(remaining: int) -> int:
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        if remaining in memo:
            return memo[remaining]
        
        min_count = float('inf')
        for coin in coins:
            result = helper(remaining - coin)
            min_count = min(min_count, result + 1)
        
        memo[remaining] = min_count
        return min_count
    
    result = helper(amount)
    return result if result != float('inf') else -1

Memoization transforms exponential time into polynomial time. Each unique subproblem (amounts 0 through amount) is solved exactly once, and each solution considers all coins. This gives us O(amount × coins) time complexity.

Bottom-Up Tabulation Solution

While memoization works, bottom-up tabulation is often cleaner and avoids recursion overhead. We build the solution from smaller subproblems to larger ones:

def min_coins_dp(coins: list[int], amount: int) -> int:
    # dp[i] = minimum coins needed for amount i
    # Initialize with infinity (impossible by default)
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins for amount 0
    
    # Build up solutions for each amount from 1 to target
    for current_amount in range(1, amount + 1):
        for coin in coins:
            if coin <= current_amount:
                # If we use this coin, we need 1 + solution for remainder
                dp[current_amount] = min(
                    dp[current_amount],
                    dp[current_amount - coin] + 1
                )
    
    return dp[amount] if dp[amount] != float('inf') else -1

Let’s trace through coins = [1, 2, 5] and amount = 11:

The answer is 3 coins: one 5 and one 1 and one 5, or equivalently 5+5+1.

Here’s the equivalent JavaScript implementation:

function minCoins(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let currAmount = 1; currAmount <= amount; currAmount++) {
        for (const coin of coins) {
            if (coin <= currAmount && dp[currAmount - coin] !== Infinity) {
                dp[currAmount] = Math.min(
                    dp[currAmount],
                    dp[currAmount - coin] + 1
                );
            }
        }
    }
    
    return dp[amount] === Infinity ? -1 : dp[amount];
}

Reconstructing the Solution

Often you need the actual coins used, not just the count. Track which coin led to each optimal solution:

def min_coins_with_path(coins: list[int], amount: int) -> tuple[int, list[int]]:
    dp = [float('inf')] * (amount + 1)
    parent = [-1] * (amount + 1)  # Track which coin was used
    dp[0] = 0
    
    for current_amount in range(1, amount + 1):
        for coin in coins:
            if coin <= current_amount:
                if dp[current_amount - coin] + 1 < dp[current_amount]:
                    dp[current_amount] = dp[current_amount - coin] + 1
                    parent[current_amount] = coin
    
    if dp[amount] == float('inf'):
        return -1, []
    
    # Backtrack to find coins used
    coins_used = []
    current = amount
    while current > 0:
        coin = parent[current]
        coins_used.append(coin)
        current -= coin
    
    return dp[amount], coins_used

# Example usage
count, coins_used = min_coins_with_path([1, 2, 5], 11)
print(f"Minimum coins: {count}")  # 3
print(f"Coins used: {coins_used}")  # [5, 5, 1] or similar

The backtracking is O(amount/min_coin) in the worst case, which doesn’t change the overall complexity.

Complexity Analysis & Optimizations

Time Complexity: O(amount × len(coins)). We iterate through each amount from 1 to target, and for each amount, we check every coin.

Space Complexity: O(amount) for the DP array. The parent array for path reconstruction adds another O(amount).

Handle edge cases explicitly:

def min_coins_robust(coins: list[int], amount: int) -> int:
    if amount == 0:
        return 0
    if not coins:
        return -1
    if amount < 0:
        return -1
    
    # Filter out coins larger than amount
    valid_coins = [c for c in coins if c <= amount]
    if not valid_coins:
        return -1
    
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for current_amount in range(1, amount + 1):
        for coin in valid_coins:
            if coin <= current_amount and dp[current_amount - coin] != float('inf'):
                dp[current_amount] = min(dp[current_amount], dp[current_amount - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

Space optimization isn’t really possible here since we need random access to previous states (unlike some DP problems where we only need the previous row).

Variations & Practice Problems

Coin Change II counts the number of combinations to make the target, not the minimum coins. The recurrence changes to summing possibilities rather than minimizing:

def coin_change_combinations(coins: list[int], amount: int) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make 0: use no coins
    
    for coin in coins:  # Iterate coins first to avoid counting permutations
        for current_amount in range(coin, amount + 1):
            dp[current_amount] += dp[current_amount - coin]
    
    return dp[amount]

Bounded Coin Supply limits how many of each coin you can use. This transforms the problem into a variant of the bounded knapsack problem.

Related Problems to Practice:

• 0/1 Knapsack: similar structure but with weights and values
• Subset Sum: can you make exactly this target from the set?
• Perfect Squares: minimum perfect squares that sum to n (coin change with coins = [1, 4, 9, 16, …])
• Minimum Cost for Tickets: a more complex real-world variant

The coin change problem is a gateway to understanding DP fundamentals. Master it, and you’ll recognize the same patterns in dozens of other problems. The key insight—building optimal solutions from optimal subsolutions—applies far beyond counting coins.