Coin Change
Mediumdp[a] = 1 + min(dp[a − coin]) · fewest coins
Build up the fewest coins for every amount using the best answers for smaller amounts.
The idea
The fewest coins to make amount a is one coin plus the fewest coins for the remaining amount, minimized over every coin. Fill amounts from 0 up to the target.
0
∞
∞
∞
∞
∞
∞
0
1
2
3
4
5
6
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, ∞, ∞, ∞, ∞, ∞, ∞.
1/8
Optimal
timeO(amount·coins)spaceO(amount)
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.