Basic example
Input
coins = [1, 2, 5], amount = 11
Output
3
11 can be made with 5 + 5 + 1 => 3 coins, which is minimum.
Full lesson preview
Find the minimum number of coins for coin change
Given coin denominations and a target amount, compute the minimum number of coins needed to make that amount, or -1 if impossible.
Python practice28 minDynamic ProgrammingAdvancedLast updated March 29, 2026
Problem statement
You are given a list of positive integers coins representing coin denominations and an integer amount representing a target sum. Return the minimum number of coins needed to make up that amount. If the amount cannot be made up by any combination of the coins, return -1. You may use an infinite number of each coin denomination.
Design an efficient algorithm using dynamic programming (tabulation) that computes the minimum number of coins required.
Task
Practice bottom-up dynamic programming (unbounded knapsack style) and learn to build a DP table for minimum counts.
Examples
Input format
Function min_coins(coins, amount) where coins is a list of positive integers and amount is a non-negative integer.
Output format
Return an integer: the minimum number of coins needed, or -1 if impossible.
Constraints
0 <= amount <= 10^4, 1 <= len(coins) <= 100, 1 <= coins[i] <= 10^4. Expected time complexity O(amount * len(coins)) or better.
Samples
Sample 1
Input
coins = [2], amount = 3
Output
-1
3 cannot be formed with only coin 2.