130. Coin Change — Minimum Coins
Make the amount exactly using any number of the available denominations. Minimize the total number of coins used, rather than the number of denomination types.
A locally largest coin choice need not be optimal. An amount of zero requires no coins, while an unreachable positive amount produces -1.
Example 1
Input
coins=[1,2,5], amount=11
Output
3
Explanation: 5+5+1 uses three coins. Two coins total at most ten, so three is optimal.
Example 2
Input
coins=[1,3,4], amount=6
Output
2
Explanation: 3+3 beats the largest-first greedy result 4+1+1, which uses three coins.
Example 3
Input
coins=[2], amount=3
Output
-1
Explanation: No sum of 2-valued coins equals 3.
Example 4
Input
coins=[], amount=0
Output
0
Explanation: The empty selection is a valid exact sum of zero.
Constraints
0 <= coins.length <= 1001 <= coins[i] <= 1040 <= amount <= 104- Duplicate denominations are allowed.
Hints
Hint 1
Suppose you knew the final coin in an optimal solution. What smaller problem remains?
Hint 2
Store the best result for every smaller amount. Which state is definitely reachable before using any coin?
Hint 3
Set dp[0]=0 and other states to amount+1; fill increasing amounts using min(dp[value-coin]+1).
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Greedy counterexample
[1,3,4]
6
2