The coin change problem is a classic computer science puzzle that asks how to make a target amount using the fewest coins possible. This FAQ covers everything from the basic definition to dynamic programming solutions. Whether you're preparing for coding interviews or just learning algorithms, this guide will break it down clearly.

What is the coin change problem?

The coin change problem asks whether you can make up a given amount using a set of coin denominations, and if so, how to minimize the number of coins. It is a fundamental exercise in dynamic programming and greedy algorithms.

For example, given coins of 1, 2, and 5, the minimum coins to make 11 is 3 (5+5+1). There are two common variants: finding the fewest coins needed and counting the number of distinct ways to make the amount.

How to solve the coin change problem?

The standard solution for the coin change problem uses dynamic programming (DP). First, create an array where each index represents an amount, and store the minimum number of coins required for that amount. Initialize the array with a large value, except dp[0] = 0.

Then, for each coin and each amount from the coin's value up to the target, update dp[amount] = min(dp[amount], dp[amount - coin] + 1). At the end, dp[target] holds the answer, or -1 if impossible.

What is the difference between the minimum coin change and the number of ways to make change?

The minimum coin change problem looks for the fewest coins to reach a target amount, while the number of ways counts all distinct combinations of coins that sum to that amount. The two problems use similar DP structures but with different recurrence rules.

For instance, with coins 1 and 2, to make amount 3, the minimum coin count is 2 (2+1), but the number of ways is 2: (1+1+1) and (2+1).

Why do we use dynamic programming for the coin change problem?

Dynamic programming is used because the coin change problem has overlapping subproblems and optimal substructure. The solution for a larger amount depends on smaller amounts that are reused many times, and DP stores these results to avoid redundant work.

This reduces the time complexity to O(n * m), where n is the target amount and m is the number of coin types, making it efficient even for large inputs.

When should I use a greedy algorithm vs dynamic programming for the coin change problem?

Use a greedy algorithm only when you know the coin denominations are canonical, meaning always picking the largest coin first yields the optimal result. For common currency systems like 1, 5, 10, 25, greedy works.

For arbitrary denominations, greedy can fail (e.g., coins 1, 3, 4 and amount 6), so you need dynamic programming to be safe. In interviews, it's best to start with the DP solution and then discuss when greedy is acceptable.

How to solve coin change problem in Python?

In Python, you can implement the dynamic programming solution in just a few lines. Initialize a list dp of length amount+1 with float('inf'), set dp[0] = 0, then loop through each coin and update the list from the coin value to the target amount.

The final value at dp[amount] is the minimum coins needed, or -1 if it remains inf. This approach is both readable and fast enough for typical interview problems.

Is the coin change problem NP-complete?

The standard coin change problem with an unlimited supply of each coin is not NP-complete; it can be solved in polynomial time using dynamic programming. However, if you restrict each coin to be used at most once, the problem becomes the subset sum problem, which is NP-complete.

So whether the coin change problem is NP-hard depends entirely on whether coins can be reused. This is a common point of confusion.

What are the best resources to learn the coin change problem?

The best resources include LeetCode (problems #322 and #518), GeeksforGeeks tutorials, and algorithm textbooks like CLRS or "Cracking the Coding Interview." YouTube video walkthroughs also provide clear, step-by-step explanations.

For practice, start with the minimum coin change problem, then move to counting the number of ways. This gives you hands-on experience with both DP variations.

Final Thoughts

Mastering the coin change problem gives you a solid foundation in dynamic programming and greedy algorithm design. The concepts extend to many other optimization problems.

Remember that the key is to recognize whether subproblems overlap and whether a greedy approach is safe. With practice, you'll quickly identify which algorithm to apply.

Whether you're coding in Python or another language, the logic remains the same. Use the resources listed here to deepen your understanding and prepare for technical interviews.