MediumArrayDynamic ProgrammingBreadth-First Search

Coin Change

1 approach, code in every language

You are given a list of coin denominations and a target amount of money. You may use each denomination any number of times.

Return the fewest number of coins needed to make up the target amount exactly. If no combination of the given coins sums to the amount, return -1.

Example 1

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

Output: 3

The amount 11 can be formed as 5 + 5 + 1, which uses three coins and no smaller count is possible.

Example 2

Input: coins = [2], amount = 3

Output: -1

With only the denomination 2 available, the odd amount 3 can never be reached, so the answer is -1.

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

Bottom-Up Dynamic Programming

Build the minimum coin count for every amount from 0 up to the target, reusing smaller answers.

Loading animation…

Intuition

Let dp[a] be the fewest coins that sum exactly to amount a. The empty amount needs zero coins, so dp[0] = 0, and every other amount starts at infinity to mark it as unreachable until proven otherwise. To make amount a, the last coin used must be some denomination c that is no larger than a, leaving the subproblem a - c; that gives the recurrence dp[a] = min over all valid c of 1 + dp[a - c]. Because every subproblem a - c is strictly smaller than a, computing amounts in increasing order guarantees the values we depend on are already final. If dp[amount] is still infinity at the end, the target cannot be assembled and we return -1.

Algorithm walkthrough

1Create a dp array of size amount + 1 filled with a sentinel that represents infinity, then set dp[0] = 0.
2Iterate a from 1 up to amount, computing the best count for each amount in turn.
3For each amount a, try every coin c with c <= a and consider 1 + dp[a - c] as a candidate.
4Keep the smallest candidate as dp[a], leaving it at infinity when no coin can complete the amount.
5After filling the table, dp[amount] holds the minimum coin count if it is finite.
6Return dp[amount] when it is reachable, otherwise return -1.

Implementation

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a and dp[a - c] + 1 < dp[a]:
                    dp[a] = dp[a - c] + 1
        return dp[amount] if dp[amount] != float('inf') else -1

Time

O(amount * coins.length)

Space

O(amount)

Every amount from 1 to the target scans all denominations once. Using amount + 1 as the infinity sentinel is safe because a valid answer never exceeds amount.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Fewest Tokens for the Charge is our own problem on the technique behind Coin Change: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free