Coin Change: Minimum Coins and Counting the Number of Ways

Coin change is two related DP problems that beginners constantly mix up. Given coin denominations and a target amount (with unlimited supply of each coin), one asks for the minimum number of coins to make the amount, and the other asks for the number of distinct ways to make it. The recurrences look similar but the loop order matters — get them straight here.

Problem 1: Minimum number of coins

State: dp[x] = fewest coins needed to make amount x.
Transition: dp[x] = min(dp[x - coin] + 1) over every coin with coin <= x.
Base case: dp[0] = 0 (zero coins make amount 0). Initialize the rest to “infinity” (unreachable).

If dp[amount] is still infinity at the end, the amount is impossible — return -1.

int coinChange(const std::vector<int>& coins, int amount) {
    const int INF = amount + 1;
    std::vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x)
                dp[x] = std::min(dp[x], dp[x - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

int coinChange(int[] coins, int amount) {
    int INF = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x)
                dp[x] = Math.min(dp[x], dp[x - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

function coinChange(coins, amount) {
  const INF = amount + 1;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++)
    for (const c of coins)
      if (c <= x)
        dp[x] = Math.min(dp[x], dp[x - c] + 1);
  return dp[amount] > amount ? -1 : dp[amount];
}

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return -1 if dp[amount] > amount else dp[amount]

Time O(amount × coins), space O(amount). Coin order doesn’t matter here because min is commutative.

Problem 2: Count the number of ways

Now count distinct combinations (order doesn’t matter — 1+2 and 2+1 are the same way).

State: dp[x] = number of ways to form amount x.
Transition: add dp[x - coin] for each coin.
Base case: dp[0] = 1 — there’s exactly one way to make 0 (use no coins).

The crucial detail: loop over coins on the outside, amounts on the inside. This counts each combination once and avoids counting permutations.

long long countWays(const std::vector<int>& coins, int amount) {
    std::vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)                         // coins OUTER
        for (int x = c; x <= amount; x++)       // amounts INNER, forward
            dp[x] += dp[x - c];
    return dp[amount];
}

long countWays(int[] coins, int amount) {
    long[] dp = new long[amount + 1];
    dp[0] = 1;
    for (int c : coins)                         // coins OUTER
        for (int x = c; x <= amount; x++)       // amounts INNER, forward
            dp[x] += dp[x - c];
    return dp[amount];
}

function countWays(coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins)                        // coins OUTER
    for (let x = c; x <= amount; x++)           // amounts INNER, forward
      dp[x] += dp[x - c];
  return dp[amount];
}

def count_ways(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                             # coins OUTER
        for x in range(c, amount + 1):          # amounts INNER, forward
            dp[x] += dp[x - c]
    return dp[amount]

Pitfall: Swap the loops in Problem 2 (amounts outer, coins inner) and you count permutations instead of combinations — 1+2 and 2+1 become two ways. That swapped version answers a different question (“number of ordered sequences”), so know which one the prompt wants.

Why this is “unbounded knapsack”

Both versions reuse each coin unlimited times — that’s the unbounded variant. Compare with 0/1 knapsack, where the 1D loop runs backward to forbid reuse. Here the inner loop runs forward precisely so each coin can be picked again. The loop direction encodes whether items are reusable.

Problem	dp[0]	Combine	Loop order
Min coins	0	`min(..., dp[x-c]+1)`	either order works
Count ways (combinations)	1	`dp[x] += dp[x-c]`	coins outer

For beginners: Greedy (“always take the biggest coin”) works for some real currencies but fails in general — e.g. coins [1, 3, 4], amount 6: greedy gives 4+1+1 (3 coins), but 3+3 is only 2. That failure is exactly why DP is needed here.

Next, tackle string transformation in edit distance, or practice on the DP exercises.