Coin Change
Compute the fewest reusable coins needed to reach the target amount, or report that it is impossible.
Problem Summary
Original task summary for this archive page. The official LeetCode prompt is linked in the header instead of being mirrored here.
Given coin denominations and a target amount, return the minimum number of coins needed to make that amount. If it cannot be formed, return \(-1\).
Because each coin may be used repeatedly, this is not a one-time selection problem. It is a repeated-choice optimization problem over smaller amounts.
Recognition Pattern
How to notice the underlying interview pattern before writing code.
This is a 1D dynamic programming problem with an unbounded knapsack-style transition.
In interviews, recognize it when:
the answer for amount \(x\) depends on answers for smaller amounts
choices can be reused multiple times
the question asks for a minimum or maximum count, not just feasibility
Key Idea
The main invariant or observation that makes the clean solution work.
Let \(dp[x]\) be the minimum number of coins needed to form amount \(x\).
For every amount \(x\), try each coin \(c\): \[ dp[x] = \min(dp[x], dp[x - c] + 1) \] whenever \(x - c \ge 0\) and \(dp[x - c]\) is reachable.
The recurrence is natural: if the last coin used is \(c\), then everything before that last step is exactly the subproblem for amount \(x - c\).
Step-by-step Reasoning
How to move from the obvious brute-force idea to the interview-ready solution.
The brute-force recursive solution tries every coin choice at every step. That quickly becomes exponential because the same remaining amount is solved again and again.
Memoization fixes the repeated work, but the bottom-up version is usually easier to explain in an interview because the state is simple and the implementation is compact.
The important observation is that amounts from \(0\) up to the target form a valid build order. Once smaller amounts are solved, each larger amount can reuse those answers immediately.
Using a large sentinel value lets the code distinguish between reachable and unreachable states cleanly.
Complexity
Time and memory costs for the implementation shown below.
Time: \(O(amount \cdot n)\), where \(n\) is the number of coin types
Space: \(O(amount)\)
C++ Solution
The exact repository source used for this LeetCode solution page.
#include <algorithm>
#include <vector>
class Solution {
public:
int coinChange(std::vector<int>& coins, int amount) {
const int unreachable = amount + 1;
std::vector<int> minimumCoins(amount + 1, unreachable);
minimumCoins[0] = 0;
for (int currentAmount = 1; currentAmount <= amount; ++currentAmount) {
for (int coin : coins) {
if (coin > currentAmount || minimumCoins[currentAmount - coin] == unreachable) {
continue;
}
minimumCoins[currentAmount] = std::min(
minimumCoins[currentAmount],
minimumCoins[currentAmount - coin] + 1
);
}
}
return minimumCoins[amount] == unreachable ? -1 : minimumCoins[amount];
}
};
Common Pitfalls
Real implementation mistakes that show up often in interviews and submissions.
If you use a large sentinel such as `amount + 1`, do not add one to an unreachable state without checking it first.
Remember that `amount = 0` should return zero coins.
Mixing this problem with the counting version (Coin Change II) can lead to the wrong recurrence or the wrong interpretation of the DP state.
Variants / Follow-ups
Nearby problems and the next generalization to learn once this pattern is stable.
This same template appears in Coin Change II, Perfect Squares, and several minimum-step or minimum-cost problems over integer states.
The main reusable lesson is to define a DP state that represents a smaller prefix of the answer space and then ask what the final move could have been.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.