Coin Change Problem

The coin change problem is a classic gateway into dynamic programming, teaching you how to break down complex optimization tasks into manageable pieces. At its core, it asks a simple question: given a set of coin denominations and a target amount of money, what is the fewest number of coins needed to make exactly that amount? Mastering this problem equips you with a powerful framework—bottom-up dynamic programming—for solving a vast array of challenges where solutions are built from smaller, overlapping subproblems.

Understanding the Problem and Its Structure

Imagine you have an unlimited supply of coins with denominations of 1, 2, and 5 cents. Your target is to make 11 cents. You could use eleven 1-cent coins, but that's not minimal. A better solution is one 5-cent coin and three 2-cent coins, totaling four coins. The optimal solution, however, is two 5-cent coins and one 1-cent coin, requiring only three coins. The coin change problem is the algorithmic challenge of finding this minimum number programmatically.

This problem possesses two key properties that make it solvable via dynamic programming. First, it has optimal substructure, meaning the optimal solution for a larger amount can be constructed from the optimal solutions of smaller amounts. If the minimum coins for 10 cents is 2, then the minimum for 11 cents might be that same 2 coins plus one more 1-cent coin. Second, it has overlapping subproblems. Calculating the minimum coins for amount 6 might require knowing the solution for amount 4, which itself is needed for calculating amount 9, and so on. A naive recursive approach would recalculate these values endlessly, but dynamic programming stores them to eliminate redundant work.

From Intuition to the Dynamic Programming Table

The leap from understanding the problem to implementing a solution involves designing a DP table. We define a one-dimensional array, dp, where dp[i] will store the minimum number of coins needed to make amount i. We initialize dp[0] = 0 because zero coins are needed to make zero cents. A critical step is to initialize all other entries to a value representing infinity (often a number larger than the target amount, like amount + 1). This signifies that those amounts are not yet reachable and allows for proper minimum comparisons.

The core logic iterates through each amount from 1 up to the target. For each amount i, we check every coin denomination c in our set. If the coin's value is less than or equal to i, it's a candidate. We look up the minimum coins needed for the remaining amount i - c in our dp table, add one (for the current coin c), and see if this yields a new minimum for dp[i]. In pseudocode, the transition is: dp[i] = min(dp[i], 1 + dp[i - c]) for all c <= i.

Let's walk through our example: target = 11, coins = [1, 2, 5].

1. dp[0] = 0
2. For i = 1: Only coin 1 applies. dp[1] = 1 + dp[0] = 1.
3. For i = 2: Coins 1 and 2 apply.

• Using coin 1: 1 + dp[1] = 2
• Using coin 2: 1 + dp[0] = 1 → dp[2] = 1

1. This process continues. For i = 6:

• Coin 1: 1 + dp[5]. We would have computed dp[5] = 1 (one 5-cent coin).
• Coin 2: 1 + dp[4]. dp[4] = 2 (two 2-cent coins).
• Coin 5: 1 + dp[1]. dp[1] = 1.
• Minimum is 1 + dp[1] = 2. So dp[6] = 2 (one 5-cent and one 1-cent coin).

1. Finally, dp[11] will be computed as 3.

Algorithm Walkthrough and Implementation Insights

The final, assembled algorithm is a clear demonstration of bottom-up DP thinking. You start by solving the smallest possible subproblem (amount 0) and systematically use those solutions to build answers to larger problems, filling the table one cell at a time. This guarantees that when you need the solution for i - c, it has already been computed and stored.

A typical implementation in Python looks like this:

def coinChange(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])

    return dp[amount] if dp[amount] != amount + 1 else -1

The outer loop builds up all amounts. The inner loop tries every coin denomination for the current amount. The final check returns -1 if the amount is unreachable (i.e., its dp value was never updated from the initial "infinity" value). The time complexity is $O(amount\ast len(coins))$, and the space complexity is $O(amount)$.

Optimization and Boundary Considerations

While the standard DP solution is efficient for most cases, understanding its boundaries is crucial. The algorithm assumes you have an unlimited supply of each coin denomination. A variant of the problem limits the quantity of each coin, which requires a different DP approach, often involving a second dimension to track coin usage.

Another consideration is the order of coins. The algorithm is generally indifferent to the order of denominations in the input list because it exhaustively tries all coins for every amount. However, you can add an early break or sorting in specific variants. More importantly, you must consider the case where no combination sums to the target. This is handled by the initialization and the final return check. If dp[amount] remains at its initial "infinity" value, no valid coin combination was found.

Common Pitfalls

1. Incorrect DP Initialization: Initializing the dp array with 0 (except for dp[0]) is a fatal error. The min() operation would never update the values because 0 is always the smallest. Always use a large sentinel value to represent "not yet computed" or "infinity."

1. Ignoring Unreachable Amounts: Failing to handle the case where the target amount cannot be formed leads to an incorrect answer. Your code must return a sentinel like -1 instead of the large sentinel value stored in the dp table. The check if dp[amount] != amount + 1 is essential.

1. Integer Overflow with Sentinel Values: In languages with fixed integer bounds, using a very large number like Integer.MAX_VALUE as your "infinity" can be dangerous. Adding 1 to it during the operation 1 + dp[i - coin] could cause an integer overflow. A safer sentinel is often amount + 1, as the maximum coins needed is the target amount using all 1-cent coins.

1. Confusing with the "Number of Ways" Variant: A common related problem asks for the total number of distinct ways to make the amount, not the minimum coins. These are solved with different DP recurrence relations. For the "number of ways" problem, the recurrence is typically dp[i] += dp[i - coin], initialized with dp[0] = 1. Applying the "minimum" logic to that problem, or vice-versa, yields completely wrong results.

Summary

• The coin change problem is a foundational dynamic programming challenge that asks for the minimum number of coins to make a target amount.
• The solution employs a bottom-up dynamic programming approach, constructing a table (dp) where dp[i] stores the minimum coins for amount i.
• The core recurrence relation is dp[i] = min(dp[i], 1 + dp[i - coin]) for each coin denomination less than or equal to i.
• Careful initialization with a sentinel value and a final check for unreachable amounts are critical to a correct implementation.
• Mastering this problem provides a template for solving a wide range of optimization problems that exhibit optimal substructure and overlapping subproblems.