Coin Change โ€” Solution

Problem

Given a list of coin denominations and a target amount, return the fewest number of coins needed to reach that amount exactly. You can use each denomination as many times as you want. Return -1 if no combination of coins can reach the target.

Example:

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

Counter-example (greedy fails): With coins = [1, 5, 11] and amount = 15, greedily picking the largest coin gives 11 + 1 + 1 + 1 + 1 = 5 coins. The actual minimum is 5 + 5 + 5 = 3 coins.

Intuition

The minimum coins needed for any amount depends only on smaller amounts โ€” if you know the cheapest way to make amount - coin for every coin, you can compute the answer for amount in one pass. This optimal substructure lets us build a solution table bottom-up from 0 to the target, reusing each result exactly once.

Approach 1 โ€” Brute Force Recursion

Try every coin at each step and recurse on the remaining amount. Without caching, overlapping subproblems are recomputed exponentially.

Steps:

  1. Base case: if remaining == 0, return 0 (no coins needed).
  2. Base case: if remaining < 0, return infinity (invalid path).
  3. Try each coin, recursing on remaining - coin.
  4. Return 1 plus the minimum valid recursive result, or -1 if none exist.
1def coin_change(coins: list[int], amount: int) -> int:
2    def min_coins(remaining: int) -> float:
3        if remaining == 0:
4            return 0
5        if remaining < 0:
6            return float('inf')
7        best = float('inf')
8        for coin in coins:
9            result = min_coins(remaining - coin)
10            best = min(best, result + 1)
11        return best
12
13    answer = min_coins(amount)
14    return answer if answer != float('inf') else -1
  • Time: O(S^n) โ€” each call branches into n recursive calls, with no caching, over up to S levels
  • Space: O(S) โ€” maximum call stack depth equals amount divided by the smallest coin

Approach 2 โ€” Bottom-Up Dynamic Programming

Build a dp table where dp[i] holds the minimum coins for amount i. Use previously solved smaller amounts to compute each new entry in a single forward pass.

Steps:

  1. Allocate dp of size amount + 1, initialized to amount + 1 as a sentinel (you can never need more coins than the amount itself).
  2. Set dp[0] = 0 โ€” zero coins are needed to make zero.
  3. For each target from 1 to amount, and for each coin:
  4. If coin <= target, update dp[target] = min(dp[target], dp[target - coin] + 1).
  5. Return dp[amount] if it is still a valid value (โ‰ค amount), otherwise -1.
1def coin_change(coins: list[int], amount: int) -> int:
2    dp = [amount + 1] * (amount + 1)  # sentinel: valid solutions need at most 'amount' coins
3    dp[0] = 0
4
5    for target in range(1, amount + 1):
6        for coin in coins:
7            if coin <= target:
8                dp[target] = min(dp[target], dp[target - coin] + 1)
9
10    return dp[amount] if dp[amount] <= amount else -1
  • Time: O(S ร— n) โ€” for each of S amounts, we try all n coin denominations once
  • Space: O(S) โ€” the dp array has one slot per amount from 0 to S

Complexity Summary

ApproachTimeSpaceWhen to use
Brute Force RecursionO(S^n)O(S)Never in production; useful only to understand why DP is needed
Bottom-Up DPO(S ร— n)O(S)Always โ€” no recursion overhead, handles large inputs without stack overflow

Common Mistakes

  • Initializing dp with 0 instead of a sentinel: Every entry except dp[0] must start at "infinity"; using 0 makes every target appear reachable with 0 coins, breaking all comparisons.
  • Overflowing when using Integer.MAX_VALUE as sentinel in Java/C++: Adding 1 to Integer.MAX_VALUE wraps to a negative number, making it look like a valid minimum. Use amount + 1 as the sentinel instead.
  • Off-by-one in dp array size: Allocating new int[amount] instead of new int[amount + 1] puts dp[amount] out of bounds โ€” the table needs indices 0 through amount inclusive.
  • Trusting greedy intuition: Picking the largest coin first fails whenever a smaller combination is cheaper. The classic trap is coins like [1, 5, 11] with amount 15, where greedy picks 11 first but the optimum skips it entirely.
  • Returning the sentinel instead of -1: When dp[amount] still equals amount + 1 after filling the table, the amount is unreachable โ€” return -1, not the sentinel value.

Related Problems

  • climbing-stairs โ€” same unbounded-choice DP recurrence, counting ways to reach a target with steps of fixed sizes
  • coin-change-ii โ€” same coins/amount setup but counts the number of distinct combinations rather than the minimum count
  • perfect-squares โ€” identical DP recurrence with perfect squares playing the role of coin denominations
  • word-break โ€” same "can we build a target from unlimited reuse of given pieces?" DP applied to strings
  • partition-equal-subset-sum โ€” bounded (0/1) variant of the same knapsack family where each item can only be used once

More Dynamic Programming solutions

View all โ†’

Ready to practice? Try it on SkillFlow

Adaptive problems, AI follow-up interviews, and a skill score that shows exactly where you need to improve.

Practice This Problem โ†’