Coin change (DP)

Unbounded knapsack variant.

dp greedy

Implement `coin_change(coins: list[int], amount: int) -> int`.

Return the fewest coins needed; return -1 if impossible.

Constraints

1 ≤ len(coins) ≤ 12; 0 ≤ amount ≤ 10^4; coins are distinct positive integers.

Example

>>> coin_change([1,5,11], 15)
3

30 points ~28 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

dp[i] = min coins for amount i; init dp[0]=0, rest=infinity.

Test Results

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