Skip to content
LEETFLIX

Coin Change

MediumArrayDPBFS
Solve on LeetCode

Medium · unbounded knapsack coins. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 322. Coin Change. The copyrighted prompt is on LeetCode. This page is a working unbounded knapsack coins for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

coins =
[1, 2, 5]
amount =
11

Output

3

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Fewest coins for each amount

dp[x] is the fewest coins that sum to x. Try every coin: dp[x] = min(dp[x], dp[x - coin] + 1).

This is unbounded knapsack. Amount 11 with {1,2,5} bottoms out at three 5+5+1 coins.

Algorithm

  1. dp[0] = 0, everything else ∞.
  2. For each amount, try each coin that fits.
  3. Return dp[amount], or −1 if it stayed ∞.
Time
O(amount · k)
Space
O(amount)
Solution.py
class Solution:    def coinChange(self, coins: list[int], amount: int) -> int:        inf = amount + 1        dp = [inf] * (amount + 1)        dp[0] = 0        for x in range(1, amount + 1):            for c in coins:                if c <= x:                    dp[x] = min(dp[x], dp[x - c] + 1)        return dp[amount] if dp[amount] < inf else -1
Watch this run

03

Interactive walkthrough

Playing “Fewest coins for each amount”. Edit the input, hit Run, then scrub.

Approach: Fewest coins for each amount

Loading animation…