Coin Change

    DSA · Intermediate

    Definition

    Find the fewest coins that make an amount, using unlimited coins of each type.

    Classic unbounded DP problem.

    Diagram

    coins 1 2 5amount 115 + 5 + 1 → 3

    Flowchart

    dp[0] = 0, others ∞For each amount aTry each coin c ≤ adp[a] = min(dp[a], dp[a−c] + 1)

    Example: Minimum coins

    coins, amt = [1, 2, 5], 11
dp = [0] + [float('inf')] * amt
for a in range(1, amt + 1):
    for c in coins:
        if c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
print(dp[amt])

    Output: 3

    Complexity

    O(amount × coins)

    Key points

    • Greedy fails for coins like [1, 3, 4]
    • Counting ways uses coins in the outer loop

    Interview questions

    Why not greedy?

    For coins [1,3,4] and 6, greedy gives 4+1+1 but 3+3 is better.

    More DSA topics

    ArraysLinked ListStackQueue