Classic Dynamic Programming: Three Coin Change Problems Explained - LeetCode by Example

The Coin Change problem is a classic introductory dynamic programming problem, but you might not know that the coin change problems on LeetCode actually form a series of three problems:

LeetCode 322. Coin Change (Medium)
LeetCode 377. Combination Sum IV (Medium)
LeetCode 518. Coin Change 2 (Medium)

Although Problem 377 isn’t called “Coin Change,” it’s essentially the same type of problem.

These three problems are quite technique-intensive, with difficulty increasing progressively. The first is a well-known introductory DP problem; the second asks for the number of combinations, requiring us to avoid both duplicates and omissions; the third is even harder, requiring an expansion to 2D dynamic programming to accurately count the number of combinations.

If you haven’t tried all three, follow along as we walk through the solutions, understanding the ideas and techniques behind each one. Let’s analyze them one by one.

(1) Problem 322: Minimum Number of Coins

LeetCode 322. Coin Change (Medium)

Given an array of coin denominations coins and a total amount, compute the minimum number of coins needed to make up that amount. If no combination of coins can make the amount, return -1. You have an infinite supply of each coin.

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

Most of you have probably seen this first problem before, and there’s no shortage of explanations online. Here we’ll still apply the four-step dynamic programming approach to solve it.

Step 1: Define the subproblem.

Let the set of coin denominations be $C = \{ c_1, c_2, \dots, c_m \}$ . We define subproblem $f(k)$ as: “the minimum number of coins to make amount $k$ .” The original problem is then $f(\text{amount})$ .

Step 2: Write the recurrence relation.

To find “the minimum number of coins to make amount $k$ ,” we can try different coins. If we use a coin of value $c$ , the problem reduces to “the minimum number of coins to make amount $k-c$ .” We pick the option that gives the smallest coin count.

This gives us the recurrence relation:

f(k) = \min_{c \in C} \{ 1 + f(k - c) \}

And don’t forget the base case:

f(0) = 0

This means when amount is 0, no coins are needed — we’ve already reached the target amount.

Step 3: Determine the computation order of the DP array.

The key to determining the computation order is to look at the dependency structure of the subproblems. Taking $C = \{ 1, 2, 5 \}$ as an example (coins of value 1, 2, and 5), $f(k)$ depends on $f(k-1)$ , $f(k-2)$ , and $f(k-5)$ , all of which are to the left of $f(k)$ . In other words, each element in the DP array only depends on elements to its left.

Dependency relationships in the DP array

Since all dependencies point to the right, the DP array should be computed from left to right.

Handling invalid elements in the DP array.

At this point, we’re very close to writing the solution, but there’s one more programming detail to handle: invalid elements in the DP array.

Some amounts may be impossible to make with the given coins. For example, with only 2-cent and 5-cent coins, we can’t make 1 cent or 3 cents. So $f(1)$ and $f(3)$ would be invalid and shouldn’t participate in the computation.

For convenience, we can represent invalid subproblems with $+\infty$ (positive infinity). Since the recurrence computes a minimum via $\min$ , an infinite value will never be chosen as the minimum. This way, invalid elements can safely participate in the computation.

In code, we observe that the maximum possible value in the DP array is amount (the case where we only have 1-cent coins, so the coin count equals the amount). We can use amount + 1 to represent positive infinity. Any value in the DP array greater than amount is considered invalid.

With all this, we can write the final solution:

public int coinChange(int[] coins, int amount) {
    // Subproblem:
    // f(k) = minimum number of coins to make amount k

    // f(k) = min{ 1 + f(k - c) }
    // f(0) = 0
    int[] dp = new int[amount+1];
    Arrays.fill(dp, amount + 1); // Initialize DP array to positive infinity
    dp[0] = 0;
    for (int k = 1; k <= amount; k++) {
        for (int c : coins) {
            if (k >= c) {
                dp[k] = Math.min(dp[k], 1 + dp[k-c]);
            }
        }
    }
    // If dp[amount] > amount, it's an invalid element.
    if (dp[amount] > amount) {
        return -1;
    } else {
        return dp[amount];
    }
}

Space optimization for this problem is cumbersome, so we’ll skip step four.

(2) Problem 377: Counting Combinations

LeetCode 377 - Combination Sum IV (Medium)

Given an array nums of distinct positive integers and a positive integer target, find the number of possible combinations that add up to target. Sequences of different orders are counted as different combinations.

Example: nums = [1, 2, 3], target = 4. All possible combinations are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Don’t be fooled by appearances — this problem looks unrelated to coin change on the surface. But if you replace nums with coins and target with amount, it becomes a genuine coin change problem:

Given an array of coin denominations coins and an amount amount, compute the number of ways to make up that amount. Sequences of different orders are counted as different ways.

The difference from the previous problem is that instead of finding the “minimum number of coins,” we need to find the “number of ways.” This raises the difficulty a notch.

The challenge with counting ways is achieving no duplicates and no omissions. When finding a minimum, overlapping subproblems are fine — you’ll still get the correct minimum. But when counting ways, overlapping subproblems lead to incorrect counts. This is something to be especially careful about.

Step 1: Define the subproblem.

Again, let the set of coin denominations be $C = \{ c_1, c_2, \dots, c_m \}$ . We define subproblem $f(k)$ as: “the number of ways to make amount $k$ .” The original problem is $f(\text{amount})$ .

Step 2: Write the recurrence relation.

We can think of each way to make change as a sequence of coins. For $f(k)$ , i.e., “the number of ways to make amount $k$ ,” consider which coin we pick first. Taking $C = \{1, 2, 5\}$ as an example, choosing 1, 2, or 5 as the first coin clearly gives different sequences. If the first coin is 1, the number of ways for the remaining amount $k-1$ is $f(k-1)$ . This gives us:

f(k) = f(k-1) + f(k-2) + f(k-5)

Generalizing to an arbitrary set of coin denominations $C$ , we get the recurrence:

f(k) = \sum_{c \in C} f(k - c)

Again, don’t forget the base case:

f(0) = 1

This means “the number of ways to make amount 0 is 1.” This is a common technique when counting ways. All $f(k)$ values ultimately trace back to $f(0)$ .

Step 3: Determine the computation order of the DP array.

The DP array and its computation order are the same as the previous problem, so we won’t repeat the discussion here.

There are no invalid elements in the DP array. Amounts that can’t be made are simply represented as $f(k) = 0$ , meaning zero ways.

Now we can write the solution. The main difficulty of this problem lies in the details of the recurrence — the final code is actually quite simple:

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target+1]; // Initialized to 0 by default
    dp[0] = 1; // Note the base case
    for (int k = 1; k <= target; k++) {
        for (int n : nums) {
            if (k >= n) {
                dp[k] += dp[k-n];
            }
        }
    }
    return dp[target];
}

(3) Problem 518: Distinct Combinations (No Duplicates)

LeetCode 518. Coin Change 2 (Medium)

Given an array of coin denominations coins and a total amount, write a function to compute the number of combinations that make up that amount. Assume you have an infinite supply of each coin denomination.

Example:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: There are four ways to make the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

The difference between this problem and the previous one is that sequences of different orders are considered the same combination. This small change causes the difficulty to spike. The recurrence we wrote for the previous problem no longer works.

For example, to make amount 5, this problem treats “2+2+1” and “1+2+2” as the same combination. We can no longer consider what the first coin is (1, 2, or 5) and then count the remaining ways as before.

So how do we eliminate duplicates like “2+2+1” and “1+2+2”? This is very much like the relationship between “permutations” and “combinations”: the previous problem treated different orderings as different ways, similar to a “permutation” problem; this problem treats different orderings as the same way, similar to a “combination” problem.

We’ve already discussed the relationship between permutation and combination problems in a previous article:

LeetCode Worked Examples | 08 Permutation and Combination Problems: Candidate Sets in Backtracking

To treat different orderings as the same combination, we only need to consider all sorted sequences and discard the rest.

For the coin problem, this means restricting the order in which coins are selected — pick larger denominations first, then smaller ones. In other words, we only allow sequences like “2+2+1” where coins appear in descending order, and disallow sequences like “1+2+2.”

How do we enforce this ordering constraint? The answer is to add another dimension to the dynamic programming, using a parameter $i$ to represent the currently available coins.

Step 1: Define the subproblem.

Let the set of coin denominations be $C = \{ c_1, c_2, \dots, c_m \}$ . The subproblem $f(i, k)$ represents the number of ways to make amount $k$ using the first $i$ coins (i.e., $c_1, \dots, c_i$ ).

Initially, $i=m$ , meaning all $m$ coins are available. If in the current step we choose the second-largest coin $c_{m-1}$ , then $i$ becomes $m-1$ , restricting future choices to coins smaller than $c_{m-1}$ .

Step 2: Write the recurrence relation.

The recurrence relation is:

f(i, k) = f(i, k - c_i) + f(i-1, k)

Where does this come from? Consider subproblem $f(i, k)$ — when making amount $k$ with coins $\{ c_1, \dots, c_i \}$ , we have two choices:

First choice: Take one coin of the largest denomination $c_i$ . Since we can take the same coin multiple times, all of $\{ c_1, \dots, c_i \}$ remain available afterward. The number of ways is $f(i, k - c_i)$ .

Second choice: Decide not to take coin $c_i$ anymore. From now on, only $\{ c_1, \dots, c_{i-1} \}$ are available. The number of ways is $f(i-1, k)$ .

You might ask: why isn’t there an $f(i-1, k-c_i)$ ? Actually, our formula already includes that case:

\begin{aligned} \text{What you might expect: } f(i, k) & \to f(i-1, k-c_i) \\ \text{What actually happens: } f(i, k) & \to f(i, k-c_i) \to f(i-1, k-c_i) \\ \end{aligned}

Thus, the original problem is $f(m, \text{amount})$ , i.e., the number of ways to make amount using all $m$ coins.

Don’t forget the base cases, which are a bit more involved for this problem:

When $k = 0$ : $f(i, 0) = 1$ . That is, “the number of ways to make amount 0 is 1” — the same technique as the previous problem.
When $i=0$ : $f(0, k) = 0$ . With no coins available, we can’t make any amount.

Step 3: Determine the computation order of the DP array.

We see that this problem has an additional dimension, making it a 2D dynamic programming problem. This makes determining the computation order even more important. For convenience, let the number of coin types be $m$ and the target amount (amount) be $n$ .

First, the valid range of the DP array is $0 \le i \le m, 0 \le k \le n$ . In the DP array, the base cases occupy the leftmost column and the top row, while the original problem is at the bottom-right corner, as shown below.

This diagram intentionally draws the DP array as a wide, flat rectangle because typically $n$ is much larger than $m$ . Here $n$ is the target amount amount, while $m$ is the number of coin types.

The dependency relationships among subproblems look like this in the DP array:

As we can see, the dependencies point to the right and downward. So we should traverse the DP array from left to right, top to bottom.

Finally, we can write the solution:

public int change(int amount, int[] coins) {
    int m = coins.length;
    int[][] dp = new int[m+1][amount+1];

    for (int i = 0; i <= m; i++) {
        for (int k = 0; k <= amount; k++) {
            if (k == 0) {
                dp[i][k] = 1; // base case
            } else if (i == 0) {
                dp[i][k] = 0; // base case
            } else {
                dp[i][k] = dp[i-1][k];
                if (k >= coins[i-1]) {
                    dp[i][k] += dp[i][k-coins[i-1]];
                }
            }
        }
    }
    return dp[m][amount];
}

Sharp-eyed readers may have noticed that this is actually a knapsack problem. It can be optimized using the standard space optimization technique for knapsack problems. Since the knapsack problem is quite advanced and many readers may not be familiar with it, we won’t go into detail here. In a future article, I’ll cover the knapsack problem and related solving techniques in depth.

Summary

Comparing the three coin change problems, we see that each one is different, with difficulty increasing progressively — making them an excellent series of practice problems.

Problem	Objective	Dimensions
322. Coin Change	Minimum number of coins	1D
377. Combination Sum IV	Number of ways	1D
518. Coin Change 2	Number of ways	2D

If you haven’t tried some of these problems yet, I strongly recommend working through them in this order after reading this article. It will deepen your understanding of the entire series.