mediumDynamic Programming

Coin Change

Find the fewest coins needed to make an amount. Each positive denomination can be reused without limit.

LeetCode ↗

Work through the cases

3 examples

Input notation

Coin denominations on line 1; nonnegative amount on line 2.

Expected result

The minimum count, or -1 if impossible.

Case 1

Input

1 3 4
6

Expected output

Case 2

Input

2
3

Expected output

-1

Case 3

Input

2 5
0

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Each coin may be used any number of times; we want the fewest coins summing to amount. This is unbounded knapsack. A raw DFS repeats sub-amounts. Let f[i][j] be the fewest coins using the first i types to make j. Skip type i via f[i-1][j]; if j ≥ x, take f[i][j-x]+1. f[0][0]=0, the rest are \infty; return -1 if impossible.

We define f[i][j] as the minimum number of coins needed to make up the amount j using the first i types of coins. Initially, f[0][0] = 0, and the values of other positions are all positive infinity.

We can enumerate the quantity k of the last coin used, then we have:

f[i][j] = \min(f[i - 1][j], f[i - 1][j - x] + 1, × s, f[i - 1][j - k × x] + k)

where x represents the face value of the i-th type of coin.

Let j = j - x, then we have:

f[i][j - x] = \min(f[i - 1][j - x], f[i - 1][j - 2 × x] + 1, × s, f[i - 1][j - k × x] + k - 1)

Substituting the second equation into the first one, we can get the following state transition equation:

f[i][j] = \min(f[i - 1][j], f[i][j - x] + 1)

The final answer is f[m][n].

The time complexity is O(m × n), and the space complexity is O(m × n). Where m and n are the number of types of coins and the total amount, respectively.

class Solution {
    public int coinChange(int[] coins, int amount) {
        final int inf = 1 << 30;
        int m = coins.length;
        int n = amount;
        int[][] f = new int[m + 1][n + 1];
        for (var g : f) {
            Arrays.fill(g, inf);
        }
        f[0][0] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= coins[i - 1]) {
                    f[i][j] = Math.min(f[i][j], f[i][j - coins[i - 1]] + 1);
                }
            }
        }
        return f[m][n] >= inf ? -1 : f[m][n];
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.