Coin Change Minimum

Find the fewest coins needed to make a given amount from unlimited coin denominations.

dynamic-programming coins minimum dp algorithm

You are given a list of positive integer coin denominations and a target amount. You have an unlimited supply of each denomination. Write a function `coin_change(coins: list[int], amount: int) -> int` that returns the minimum number of coins needed to make exactly the target amount. If it is impossible, return -1. Assume that `coins` contains distinct positive integers and `amount >= 0`.

Constraints

1 <= len(coins) <= 100, 1 <= coin value <= 10^4, 0 <= amount <= 10^4. The solution should run in O(amount * len(coins)) time and O(amount) space.

Example

>>> coin_change([1,2,5], 11)
3  # 5+5+1
>>> coin_change([2], 3)
-1
>>> coin_change([1], 0)
0
>>> coin_change([2,5,10,1], 27)
4  # 10+10+5+2

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about building up from amount 0 to the target using previously computed smaller amounts.

Initialize an array with a large value (like infinity) and set dp[0] = 0.

For each amount, try every coin and see if using that coin leads to a better count.

If dp[amount] remains infinity, return -1.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.