DP: Coin Change and Making Change Problems

Making exact change for a given amount is a deceptively simple task that reveals deep principles of algorithm design. In computer science, coin change problems are classic gateways into dynamic programming (DP), a method for solving complex problems by breaking them down into simpler overlapping subproblems. Mastering these problems teaches you how to optimize for minimum resources and count possibilities systematically—skills applicable from financial software to game theory.

The Classical Minimum Coin Change Problem

The most fundamental question is: given an unlimited supply of coins of specified denominations, what is the minimum number of coins needed to make a target amount? For example, with coins [1, 2, 5] cents and a target of 11 cents, the optimal solution is 5+5+1 (3 coins). A greedy approach—always taking the largest coin possible—works for some coin systems (like US currency) but fails for others, like [1, 3, 4] cents for a target of 6. The greedy method gives 4+1+1 (3 coins), while the optimal is 3+3 (2 coins).

This is where dynamic programming shines. You define dp[s] as the minimum number of coins required to make amount s. You build the solution from the bottom up, starting with dp[0] = 0. For every amount s from 1 to your target S, and for every coin c in your list, you check if the coin can be used (i.e., c <= s). The core recurrence relation is: $$dp[s]=\underset{c\le s}{\min }(1+dp[s-c])$$

This formula says: the best way to make amount s is to take one coin of denomination c and then look up the optimally pre-computed solution for the remaining amount s-c. You try all possible c and choose the minimum. The time complexity is $O(n\cdot S)$, where n is the number of coin denominations and S is the target amount. The space complexity is $O(S)$ for the dp array.

Counting All Ways to Make Change

A related but distinct problem asks: how many distinct combinations of coins (order does not matter) sum to the target amount? With unlimited coins [1, 2, 5] and target 5, the ways are: 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1. Notice that 2+1+2 is not considered different from 2+2+1.

The DP approach for counting requires careful state definition to avoid counting permutations of the same set multiple times. The standard method uses a 2D DP approach conceptually, but a clever one-dimensional array is often used. The key is to structure the loops to enforce order. You iterate through coins one by one. For each coin c, you then iterate through amounts s from c up to S and update the count: ways[s] += ways[s - c]

By processing coins in an outer loop, you ensure that combinations are built in a canonical order (e.g., using larger coins first, then smaller ones), so you count each unique set only once. Initializing ways[0] = 1 represents the one way to make amount zero: using no coins. This algorithm also runs in $O(n\cdot S)$ time and $O(S)$ space.

Handling Limited Coin Supply and Space Optimization

In real-world scenarios, you often have a limited supply of each coin. This transforms the problem, making it more akin to the subset sum problem. The DP solution now needs to track both the amount and the usage of coins. A standard approach is to use a 2D DP table dp[i][s] representing the number of ways (or minimum coins) to make amount s using only the first i coin types with their limited quantities. Alternatively, you can adapt the one-dimensional DP array but iterate the amount in reverse (from S down to c) when counting ways. This reverse order ensures that each coin is used at most once per inner-loop iteration, effectively modeling a limited supply of one coin per denomination. For true quantity limits, a more detailed state is needed.

Space optimization to $O(S)$ is a crucial engineering skill. As shown in the counting solution, by using a single array dp[s] and updating it iteratively, you achieve significant memory savings. For the minimum coin problem, the same applies: you maintain a one-dimensional min_coins[s] array and update it by looping over coins and amounts. The order of loops matters less for the minimum coin problem with unlimited supply, but for counting with unlimited supply, the coin-first order is essential to avoid permutations.

Connections to Integer Partition and Subset Sum

The coin change problem is a specific instance of broader combinatorial problems. The subset sum problem asks whether there is a subset of a given set of numbers that adds to a target. The coin change counting problem, with each coin usable once (limited supply of 1), is exactly subset sum counting. The minimum coin change problem generalizes to finding the smallest subset that sums to the target.

Furthermore, the counting problem with an unlimited supply of coins of denomination 1 is essentially the integer partition problem, which counts the number of ways to write an integer as a sum of positive integers. Understanding the coin change DP provides the foundational framework for tackling these more general problems, where the "coins" become the numbers you can use, and the recurrence relations grow more complex but follow similar overlapping subproblem principles.

Common Pitfalls

1. Incorrect Initialization in Counting Problems: Forgetting to set ways[0] = 1 is a common error. This base case is not intuitive but is logically necessary: there is exactly one way to make amount zero—by selecting no coins. Without this, the entire DP table may remain zero.

1. Counting Permutations Instead of Combinations: If you accidentally swap the loops—iterating amounts in the outer loop and coins in the inner loop—you will count different orders of the same coin set as distinct. For example, 1+2 and 2+1 would be counted separately. Always place the coin iteration on the outside to enforce a canonical order and count true combinations.

1. Misapplying the Greedy Algorithm: Assuming the greedy algorithm (always pick the largest coin) works for all coin systems leads to incorrect minimum coin counts. Always verify if your coin denominations are "canonical" (like US coins) or if a DP solution is required. When in doubt, use DP.

1. Overlooking Integer Overflow in Counting: The number of ways to make change can grow exponentially. Using a standard 32-bit integer for a large target amount can easily cause overflow. In practice, you should use a larger data type (like long long in C++) or implement modular arithmetic if only the remainder is needed.

Summary

• The minimum coin change problem is solved via bottom-up DP using the recurrence dp[s] = min(1 + dp[s-c]) for all coins c, yielding an $O(n\cdot S)$ time solution.
• The counting change problem requires careful loop ordering (coins outer loop, amounts inner loop) to count unique combinations, not permutations, using the update ways[s] += ways[s-c].
• Both problems can be optimized to use only $O(S)$ space by using a one-dimensional DP array updated iteratively.
• Variants with limited coin supply require modified DP approaches, often involving reverse iteration or multi-dimensional states, connecting them to the subset sum problem.
• These DP formulations provide a foundational framework for solving related combinatorial problems like integer partition and generalized subset sum.