Minimum Coins
HardUnbounded: stay on the same coin
Problem
Return the minimum number of coins (unlimited supply) to make a target amount, or -1.
Build the fewest coins for every amount from the fewest for smaller amounts.
The idea
For each amount, take the best over every coin of 1 + the answer for (amount - coin). Because coins are unlimited, the recursion does not advance the coin index when it takes one.
The trick
- Initialise with a large sentinel and return -1 if it survives.
- Iterate amounts ascending so smaller answers are ready.
- O(amount × coins).
Step 1 of 8. dp[a] = fewest coins to make amount a. Coins 1, 3, 4. dp[0] = 0, the rest start at ∞. Values: 0, ∞, ∞, ∞, ∞, ∞, ∞.
Unbounded knapsack.
1const dp = Array(amount + 1).fill(Infinity);2dp[0] = 0;3for (let a = 1; a <= amount; a++)4 for (const c of coins)5 if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);6return dp[amount] === Infinity ? -1 : dp[amount];Input
- array
- [0, ∞, ∞, ∞, ∞, ∞, ∞]
Memory
- a
- —
- a−c
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- coins = [1, 2, 5], amount = 11
- Output:
- 3
- Explanation:
- 5 + 5 + 1 uses just 3 coins.
Example 2
- Input:
- coins = [2], amount = 3
- Output:
- -1
- Explanation:
- You can't make 3 from 2s → -1.
Example 3
- Input:
- coins = [1], amount = 0
- Output:
- 0
- Explanation:
- Zero amount needs zero coins.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.