codejump
HardPro challengePython

Dynamic Programming — Coin Change

PythonDynamic ProgrammingAlgorithms

Given a list of coin denominations and a target amount, return the minimum number of coins needed to make amount. Return -1 if it's impossible.

Examples

  • solve([1, 5, 10, 25], 36) → 3 (25 + 10 + 1)
  • solve([2], 3) → -1
  • solve([1], 0) → 0

Constraints

  • Use bottom-up dynamic programming (O(amount × len(coins))).
  • 1 ≤ len(coins) ≤ 12, 0 ≤ amount ≤ 10_000.

Sample tests

Test #125+10+1 = 3 coins
Input: [[1,5,10,25],36]
Output: 3
Test #2Impossible — no odd coins
Input: [[2],3]
Output: -1
Test #3Amount 0 — zero coins
Input: [[1],0]
Output: 0
Test #45+5+1 = 3 coins
Input: [[1,2,5],11]
Output: 3
← All challenges