Mid-levelMid (3–6 yrs)CodingPythonAmazonGoldman SachsPaytm

DP coin change interview

Derive the DP recurrence for Coin Change (fewest coins). What are common bugs?

Answers use simple, clear English.

Audio N/A

Time: O(amount * k)Space: O(amount)

Quick interview answer

dp[0]=0; dp[a]=min(dp[a-c]+1 for coin c<=a) else inf. Unbounded knapsack: loop amounts outer or coins outer carefully. Bugs: treating as 0/1 knapsack, not handling unreachable (return -1), int overflow in other languages, mutating coins order assumptions.

Detailed answer

Real example & use case

Vending machine minimal coins for amount.

Pros & cons

Pros: standard DP. Cons: large amount space; greedy fails for some coin sets.

Code example

def coin_change(coins: list[int], amount: int) -> int:
    dp = [0] + [10**9] * 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 -1 if dp[amount] >= 10**9 else dp[amount]

Practice code · python (view only · no execution)

def coin_change(coins: list[int], amount: int) -> int:
    dp = [0] + [10**9] * 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 -1 if dp[amount] >= 10**9 else dp[amount]

#dsa#dp#coin-change