Coin Change

Difficulty: Medium · Topic: Dynamic programming

Given coin denominations coins and a target amount, return the minimum number of coins that sum to amount, or -1 if it can't be made. Build a 1D table dp[a] = fewest coins for amount a, trying every coin for each amount.

Examples

coin_change([1,2,5], 11)
→ 3

5 + 5 + 1.

coin_change([2], 3)
→ -1

coin_change([1], 0)
→ 0

Target complexity: time O(amount · k), space O(amount)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.