Coin Change

Find the fewest coins needed to make a target amount.

Pattern

Unbounded Knapsack

This problem follows the Unbounded Knapsack pattern, commonly found in the 1-D Dynamic Programming category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

dp[amount] = min(dp[amount], dp[amount - coin] + 1) for each coin.

Key Insight

This is unbounded knapsack — each coin can be used unlimited times. The order of the loops (amount outer, coins inner) handles this correctly.

Step-by-step

1Create dp array of size (amount + 1), initialized to infinity
2dp[0] = 0 (zero coins needed for amount 0)
3For each amount from 1 to target:
4For each coin, if coin <= amount: dp[amount] = min(dp[amount], dp[amount - coin] + 1)
5Return dp[amount] if it's not infinity, else -1

Pseudocode

dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

Complexity Analysis

Time Complexity

O(amount * n)

Space Complexity

O(amount)

Master this pattern with YeetCode

Practice Coin Change and similar 1-D Dynamic Programming problems with flashcards. Build pattern recognition through active recall.

Practice this problem

Previous← Palindromic Substrings NextWord Break →