Coin change

Lesson 7.5 · Medium · Table of amounts · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Given coin values and an amount, find the fewest coins that make the amount exactly.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

zero00

∞1

∞2

∞3

∞4

∞5

∞6

∞7

∞8

∞9

∞10

∞11

∞12

∞13

∞14

∞15

∞16

∞17

∞18

dp[x] = fewest coins to make x. Zero coins make 0. Everything else starts unknown (∞).

coins [1, 6, 10]

1 / 20

The idea

Complexity

Time	Space	Why
`O(amount × coins)`	`O(amount)`	Every amount tries every coin once.

In Python

def coin_change(coins, amount):
    dp = [0] + [float('inf')] * amount
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return -1 if dp[amount] == float('inf') else dp[amount]

</> Now code it →Try it on LeetCode: Coin Change →

Summary: say it in the interview

Fill a table from 0 up. To make amount i, try each coin c: use one c, then add the best answer for i - c. Keep the smallest. Greedy (largest coin first) can fail, this cannot.
Time O(amount × coins), space O(amount). Every amount tries every coin once.