Coin Change

Medium#3221d array

You get coin values, as many coins of each as you like, and an amount. Pay the amount exactly with as few coins as possible, or return -1 if it cannot be done. Our example: coins [3, 5, 6], amount 10 — 2 coins, 5 + 5.

322 Coin ChangeWalkthrough · 1×

Example: coins [3, 5, 6], amount 10. Watch amount 10: the largest coin 6 leads nowhere.

coins356dp0∞1∞2∞3∞4∞5∞6∞7∞8∞9∞10∞
this amount, this coinfilled, ∞ if not payableread fromanswer and its coins

dp[a]: the fewest coins that pay exactly a. At first every amount is ∞, not payable yet

01/44
restart · back · play · step
Speed
1function coinChange(coins, amount):
2 dp = array of size amount + 1, all ∞
3 dp[0] = 0 // nothing to pay
4 for a from 1 to amount:
5 for each c in coins:
6 if c <= a:
7 dp[a] = min(dp[a], dp[a - c] + 1)
8 if dp[amount] == ∞:
9 return -1
10 return dp[amount]
state
dp
[∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
a
–
c
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Whatever coins pay a, one of them is paid last. If it is c, the rest pays a − c, and in the best case with dp[a − c] coins. So dp[a] is the smallest dp[a − c] + 1 over all coins.
  2. ∞ keeps the amounts that cannot be paid out of the minimum: ∞ + 1 is still ∞. That is why the coin 6 gives nothing at 10 — the 4 left over is ∞ — and the largest coin is not always the right one.
  3. The amounts go up from 1, and a − c is always smaller than a, so every cell a cell reads is already final.

Complexity

Time O(amount × coins): every amount tries every coin once. Memory O(amount): one cell per amount from 0 up.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.