Sign in
Skip to solution
mediumDSA

How do you solve the coin change problem?

368 views
01

Understand the problem

Explain coin change DP.

dpcoin-change
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

For minimum coins, build dp[amount] = 1 + min over coins of dp[amount - coin], base dp[0]=0. It's a bottom-up DP in O(amount × coins). The count-of-ways variant iterates coins in an outer loop to avoid permutations.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Min coins (bottom-up DP)
Run Playground
def coin_change(coins, amount):
    dp = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1


# --- demo ---
print(coin_change([1, 3, 4], 6))   # 2  (3+3, beats greedy's 4+1+1)
print(coin_change([2], 3))         # -1 (impossible)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 77 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track