Coin Change: Bottom-Up DP Explained

Coin Change is the textbook example of unbounded knapsack expressed in a friendly way. It is also one of the most common “medium that interviewers expect Easy fluency on” problems. Master it once and you have a template for any minimum-coins, minimum-jumps, or minimum-steps DP question.

The Problem

You are given an integer array coins of distinct positive denominations and an integer amount. Return the minimum number of coins needed to make up amount. You may use each coin an unlimited number of times. If it is impossible to make the amount, return -1.

Example inputs and outputs:

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

Input:  coins = [2], amount = 3
Output: -1
Explanation: No combination of 2s makes 3.

Input:  coins = [1], amount = 0
Output: 0
Explanation: Zero coins for amount 0.

A common trap: greedy “use the largest coin first” works for the US currency system but fails in general. For coins = [1, 3, 4] and amount = 6, greedy gives 4 + 1 + 1 = 3 coins while the optimum is 3 + 3 = 2 coins. That counterexample is worth memorizing.

Intuition

Define dp[total] as the minimum number of coins required to make total. The last coin used must be some c in coins, leaving the subproblem dp[total - c]. Taking the min over all valid last coins gives the recurrence dp[total] = 1 + min(dp[total - c]). The state space is only amount + 1, so we sweep bottom up, using amount + 1 itself as the “unreachable” sentinel (any real answer is at most amount, so the sentinel can never beat a real value).

Explanation with Example

Take coins = [1, 2, 5], amount = 11. Build the table left to right:

dp[0]  = 0
dp[1]  = dp[0] + 1 = 1                      (use 1)
dp[2]  = min(dp[1]+1, dp[0]+1) = 1          (use 2)
dp[3]  = min(dp[2]+1, dp[1]+1) = 2          (2+1)
dp[4]  = min(dp[3]+1, dp[2]+1) = 2          (2+2)
dp[5]  = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1 (use 5)
dp[6]  = min(dp[5]+1, dp[4]+1, dp[1]+1) = 2 (5+1)
dp[7]  = 2  (5+2)
dp[8]  = 3  (5+2+1)
dp[9]  = 3  (5+2+2)
dp[10] = 2  (5+5)
dp[11] = 3  (5+5+1)

Final answer: 3. The table records the optimum for every subamount along the way, which is part of why DP is so reusable.

amt    0  1  2  3  4  5  6  7  8  9 10 11
dp     0  1  1  2  2  1  2  2  3  3  2  3

dp[a] = 1 + min( dp[a-c] for c in coins if a-c >= 0 )

dp[11] = 1 + min(dp[10], dp[9], dp[6])
     = 1 + min(2, 3, 2) = 3   (5+5+1)

Code

We use amount + 1 as the sentinel for “unreachable” because it is strictly greater than any valid answer.

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

import java.util.*;

class Solution {
    public 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 total = 1; total <= amount; total++) {
            for (int c : coins) {
                if (c <= total) {
                    dp[total] = Math.min(dp[total], dp[total - c] + 1);
                }
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

#include <vector>
#include <algorithm>
using namespace std;

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

Edge Cases

• amount = 0: return 0. The base case dp[0] = 0 handles this naturally.
• No combination reaches the amount: return -1. The sentinel check catches this.
• A single coin equal to the amount: return 1.
• A single coin larger than the amount, with no smaller denomination: return -1.
• Duplicate coins: not allowed by constraints, but the algorithm is robust to them.
• Large amount and small coins: time is O(amount * len(coins)), still very fast.

Complexity Analysis

• Time: O(amount * k) where k = len(coins). We fill amount + 1 cells and do k work per cell.
• Space: O(amount) for the DP table.

The brute force without memoization is exponential, roughly O(k^amount). With memoization it becomes O(amount * k) time and O(amount) space, equivalent to the bottom-up version.

How to Explain It in an Interview

Walk through the problem like this:

1. Reject greedy with the [1, 3, 4] counterexample. This shows you understand why DP is necessary.
2. Define the state: dp[total] is the minimum coins to make total.
3. State the recurrence: dp[total] = 1 + min(dp[total - c]) over all coins c <= total.
4. Pick the sentinel amount + 1 and explain why it is safe.
5. Code bottom-up because it avoids stack depth and is simpler to reason about.
6. Trace one small example, then state the final time and space complexity.

Bonus points if you mention that the same recurrence solves “minimum jumps”, “minimum number of squares summing to n”, and other minimization problems. That generalization is the real takeaway.

Related Problems

• Coin Change II: count the number of combinations rather than minimize coins.
• Perfect Squares: minimum count of perfect squares summing to n; same recurrence.
• Minimum Number of Refueling Stops: another min-count DP.
• Jump Game II: minimum jumps to reach the end.

Wrap up

Coin Change is one of the highest-leverage DP problems to internalize. The unbounded-knapsack recurrence shows up constantly, and the sentinel trick generalizes to many minimization questions. Build the bottom-up version from memory, trace it on [1, 2, 5] and [1, 3, 4], then move on to /blog/dynamic-programming-classic-problems for harder variants. The pattern is more important than the problem.