Coin Change — Unbounded Knapsack DP for Minimum Coins

Problem Statement#

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

Example 1:

Input:  coins = [1, 5, 10, 25], amount = 36
Output: 3
Explanation: 25 + 10 + 1 = 36. Three coins.

Example 2:

Input:  coins = [2], amount = 3
Output: -1
Explanation: Cannot make 3 with only coins of denomination 2.

Example 3:

Input:  coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 5 + 5 + 1 = 11. Three coins.

Why This Problem Matters#

Coin Change (LeetCode 322) is one of the most important DP problems you will encounter in FAANG interviews. Amazon includes it in coding assessments. Google uses it to probe knowledge of the unbounded knapsack pattern. Microsoft reaches for it in onsite loops. It appears in every major DP curriculum — Blind 75, NeetCode 150, Grind 169 — for a reason: it is the canonical example of minimization over an unbounded selection of items.

The unbounded knapsack model — where each "item" (coin) can be used infinitely many times and you want to minimize a cost (number of coins) subject to an exact target — recurs across system design problems (change dispensing machines), financial optimization, and any resource allocation scenario with a divisible target.

Understanding this problem deeply means you can immediately recognize and solve: Perfect Squares (LC 279), Coin Change II (LC 518), Minimum Cost to Reach Destination, and dozens of similar problems.

The Core Insight#

Define dp[i] as the minimum number of coins needed to make amount i. You want dp[amount].

For each amount i, try every coin denomination c. If c <= i, then you can use coin c and still need to make i - c more. The minimum coins for amount i using coin c is dp[i - c] + 1.

Take the minimum over all valid coins: dp[i] = min(dp[i - c] + 1 for all c in coins if c <= i)

Base case: dp[0] = 0 — zero coins needed to make amount 0.

Initialization: dp[i] = infinity (or amount + 1) for all i > 0, representing "not yet reachable." After filling the table, if dp[amount] is still infinity, return -1.

Why this is correct: For every way to make amount i, the last coin used was some denomination c. Removing that coin leaves amount i - c, which requires dp[i - c] coins optimally. So dp[i] = dp[i - c] + 1 and we minimize over all c.

Unbounded nature: Each coin can be used multiple times because we access dp[i - c] with c <= i, and dp[i - c] itself was computed using the same coin set (including c again). This differs from the 0/1 knapsack where each item is used at most once.

Building the DP Solution#

Step 1 — Naive Recursion (Exponential)#

# Python — naive recursion, exponential — illustrative only
def coinChange(coins, amount):
    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        return min(dp(remaining - c) + 1 for c in coins)
 
    result = dp(amount)
    return result if result != float('inf') else -1

// JavaScript — naive recursion
function coinChange(coins, amount) {
    function dp(remaining) {
        if (remaining === 0) return 0;
        if (remaining < 0) return Infinity;
        return Math.min(...coins.map(c => dp(remaining - c) + 1));
    }
    const result = dp(amount);
    return result === Infinity ? -1 : result;
}

This recomputes the same remaining amounts repeatedly, leading to exponential time.

Step 2 — Top-Down Memoization (O(amount * len(coins)) time, O(amount) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        @lru_cache(maxsize=None)
        def dp(remaining: int) -> int:
            if remaining == 0:
                return 0
            if remaining < 0:
                return float('inf')
            return min(dp(remaining - c) + 1 for c in coins)
 
        result = dp(amount)
        return result if result != float('inf') else -1

// JavaScript — top-down memoization
var coinChange = function(coins, amount) {
    const memo = new Map();
 
    function dp(remaining) {
        if (remaining === 0) return 0;
        if (remaining < 0) return Infinity;
        if (memo.has(remaining)) return memo.get(remaining);
        let result = Infinity;
        for (const c of coins) {
            const sub = dp(remaining - c);
            if (sub !== Infinity) result = Math.min(result, sub + 1);
        }
        memo.set(remaining, result);
        return result;
    }
 
    const result = dp(amount);
    return result === Infinity ? -1 : result;
};

Step 3 — Bottom-Up Tabulation (O(amount * len(coins)) time, O(amount) space)#

# Python — bottom-up tabulation
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
 
        for i in range(1, amount + 1):
            for c in coins:
                if c <= i:
                    dp[i] = min(dp[i], dp[i - c] + 1)
 
        return dp[amount] if dp[amount] != float('inf') else -1

// JavaScript — bottom-up tabulation
var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
 
    for (let i = 1; i <= amount; i++) {
        for (const c of coins) {
            if (c <= i && dp[i - c] !== Infinity) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }
 
    return dp[amount] === Infinity ? -1 : dp[amount];
};

Optimized Solution#

The bottom-up tabulation is already optimal. There is no space optimization possible beyond O(amount) since we need the full dp array. The final submission-ready solution:

# Python — final solution, O(amount * n) time, O(amount) space
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for c in coins:
                if c <= i:
                    dp[i] = min(dp[i], dp[i - c] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

// JavaScript — final solution
var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (const c of coins) {
            if (c <= i) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
};

Note: using amount + 1 as the sentinel infinity is safe because you can always make amount amount using amount coins of denomination 1 (assuming coins include 1). If coins do not include 1, the sentinel is safe because no valid answer exceeds amount.

Visual Dry Run#

Input: coins = [1, 2, 5], amount = 11

Build dp[0..11]:

Answer: 3. Use coins 5 + 5 + 1 = 11.

Complexity Analysis#

Where n = len(coins) and amount can be up to 10^4. The total operations are at most 10^4 * 12 = 120,000 — very fast.

Common Mistakes#

1. Initializing dp[i] = 0 instead of infinity. Zero means "0 coins needed," which is only true for dp[0]. All other positions must start at infinity so that unreachable amounts are identified correctly.

2. Using amount instead of float('inf') as the sentinel, then not returning -1. If you use amount + 1 as sentinel, remember to check dp[amount] > amount (not == float('inf')) before returning -1.

3. Inner loop ordering: coins first vs. amounts first. For Coin Change (minimize count, unlimited coins), iterating over amounts in the outer loop and coins in the inner loop is standard. For Coin Change II (count combinations, order matters), the loop order is different. Do not mix them up.

4. Checking c <= i versus c <= i - 1. The condition is c <= i because you need i - c >= 0. c <= i ensures dp[i - c] is a valid index.

5. Returning dp[amount] when it equals the sentinel. Always check if the sentinel value survived (meaning the amount is unreachable) and return -1 in that case.

6. Thinking this problem requires greedy. The greedy approach (always use the largest coin that fits) works for standard currency denominations but fails for arbitrary coin sets. Example: coins = [1, 3, 4], amount = 6. Greedy: 4+1+1 = 3 coins. DP: 3+3 = 2 coins.

Interview Tips#

State the DP state definition explicitly. Say: "I define dp[i] as the minimum number of coins to make amount i. My base case is dp[0] = 0. For each amount from 1 to target, I try every coin and take the minimum."

Explain why greedy fails. Mention: "Greedy would always pick the largest coin, but that fails for coins like [1, 3, 4] with amount 6 — greedy gives 3 coins (4+1+1) while DP finds 2 coins (3+3)."

Connect to unbounded knapsack. "This is the unbounded knapsack problem: unlimited quantity of each coin type, minimize the count to reach an exact target weight."

Distinguish from Coin Change II. "Coin Change asks for minimum count of coins. Coin Change II asks for total number of combinations. Same coin set, completely different DP table and loop structure."

Follow-up Questions#

Q: What if you need to count the number of ways to make the amount (not minimum coins)? That is Coin Change II (LC 518). Change dp[i] = min(...) to dp[i] += dp[i - c]. Initialize dp[0] = 1.

Q: What if each coin can be used at most once? This becomes the 0/1 knapsack. Iterate coins in the outer loop and amounts in reverse (right to left) to prevent reuse.

Q: What if you need to output the actual coins used, not just the count? Track parent[i] = c for the coin c that gave dp[i] its minimum value. Reconstruct by following parent pointers from amount to 0.

Q: What if the coin denominations change per query? Recompute the dp array for each query. There is no known general approach to incrementally update the dp table when denominations change.

Q: What is the relationship to Perfect Squares (LC 279)? Perfect squares are the "coin denominations" (1, 4, 9, 16, ...) and the "amount" is n. The recurrence is identical: dp[i] = min(dp[i - j*j] + 1) for all j*j <= i.

Key Takeaways#

• Define dp[i] as the minimum coins to make amount i. Base case: dp[0] = 0. Fill from 1 to amount.
• Recurrence: dp[i] = min(dp[i - c] + 1 for all c in coins if c <= i). Take the minimum over all usable coins.
• Initialize dp[i] = infinity (or amount + 1) to represent unreachable amounts. Return -1 if dp[amount] remains at the sentinel.
• This is the unbounded knapsack minimization pattern — each coin can be used multiple times because dp[i - c] itself allows further use of the same coin.
• Greedy fails on arbitrary coin sets — always use DP.
• Coin Change (minimize count) and Coin Change II (count combinations) have the same structure but different operators and loop orderings.