← Back to DSA Animator
Coin Change LC #322 Medium Unbounded Knapsack DP
Problem

You are given an integer array coins representing coins of different denominations and an integer amount. Return the fewest number of coins to make that amount. If impossible, return -1. You may use each coin infinite times.

Example 1
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2
Input: coins = [2], amount = 3
Output: -1
Constraints: 1 ≤ coins.length ≤ 12  |  0 ≤ amount ≤ 10⁴
Try Examples
Custom:
Approach
Unbounded Knapsack — dp[a] = min coins for amount a
For each amount a, try every coin c ≤ a. dp[a] = min(dp[a], dp[a-c] + 1). dp[0]=0 base case.
DP Table
Load an example to begin.
Variables
amount a
—
coin c
—
source dp[a-c]
—
candidate
—
Step Logic
Press ▶ Play or Next Step to begin.
🪙
Ready
0 / 0
Select an example and press Play.
Algorithm
1
dp[a] = min coins for amount a. dp[0]=0, rest=∞
2
For each amount a, try every coin c ≤ a
3
dp[a] = min(dp[a], dp[a-c] + 1)
4
Return dp[amount] or -1 if still ∞
Time
O(amount × coins)
Space
O(amount)
Why This Works

Unbounded knapsack: each coin can be used multiple times. For each target amount a, we try every coin c that fits. If we use coin c, we need 1 + min coins for a−c, so candidate = dp[a−c] + 1. We keep the minimum. dp[0]=0 is the base case.