☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Minimum Coins (DP - 20)

Hard TUF ID 2802 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array coins of distinct coin denominations and a target amount. You have an unlimited supply of every denomination. Return the fewest coins whose values add up to exactly amount, or -1 if no combination of coins makes it.

This is LeetCode 322, Coin Change. Constraints: 1 ≤ coins.length ≤ 12, 1 ≤ coins[i] ≤ 2^31 - 1, 0 ≤ amount ≤ 10^4.

Example 1

coins = [1, 2, 5], amount = 11
answer = 3          // 5 + 5 + 1

Example 2

coins = [2], amount = 3
answer = -1         // any number of 2s is even

Why greedy is not enough

With Indian or US currency, “take the largest coin that fits, repeat” happens to be optimal. For arbitrary denominations it is not. With coins = [1, 3, 4] and amount = 6, greedy takes 4 + 1 + 1 (three coins), but 3 + 3 uses two. Taking the big coin early can leave a remainder that only small coins can fill. We have to consider, for every denomination, how many copies to use, which is what the DP does.

The unbounded pick / not-pick recursion

This is the first problem in this series where an element may be used more than once. The state stays (i, t): denominations coins[0..i] are still allowed and t is the amount still to make. The only change from 0/1 subset problems is in the “take” branch:

Staying at i is what makes the supply unlimited. The recursion still terminates because t strictly decreases whenever we stay.

Base case at i = 0: only coins[0] is left, so t is reachable exactly when coins[0] divides it, using t / coins[0] coins. That covers t = 0 too (zero coins).

Impossibility is represented by INF = 10^9 rather than Integer.MAX_VALUE, so that 1 + INF cannot overflow into a negative number and win a min. Every method converts a final result ≥ INF into -1.

f(0, t) = t / coins[0]  if coins[0] divides t,  else INF
f(i, t) = min( f(i - 1, t),  1 + f(i, t - coins[i])  if coins[i] ≤ t )
answer  = f(n - 1, amount), or -1 if that is INF

Approach 1: Recursion

Intuition. Implement the recurrence directly. Each call decides one thing: use another copy of coins[i], or never use coins[i] again.

Algorithm.

  1. If i == 0, return t / coins[0] if divisible, else INF.
  2. notTake = f(i - 1, t).
  3. take = 1 + f(i, t - coins[i]) if coins[i] ≤ t, else INF.
  4. Return min(notTake, take).
static int recursive(int[] coins, int amount) {
    int res = solve(coins.length - 1, amount, coins);
    return res >= INF ? -1 : res;
}

static int solve(int i, int t, int[] coins) {
    if (i == 0) return t % coins[0] == 0 ? t / coins[0] : INF;    // only coins[0] left: it must divide t
    int notTake = solve(i - 1, t, coins);
    int take = coins[i] <= t ? 1 + solve(i, t - coins[i], coins) : INF;   // stay on i: unlimited supply
    return Math.min(notTake, take);
}

Complexity. Time is exponential: the depth can reach amount (when a coin of value 1 is taken repeatedly) and each call branches twice, so O(2^amount) is a safe bound. Space O(amount) for the recursion depth.

Approach 2: Memoization

Intuition. The answer for (i, t) does not depend on how we got there, and there are only n · (amount + 1) such states. Store each one. Real answers are ≥ 0 and INF is a real “impossible” value, so -1 is free to mean “not computed”.

Algorithm.

  1. Allocate dp[n][amount + 1] filled with -1.
  2. Same recursion; return the cached value when present, store every computed value.
  3. Convert INF to -1 at the end.
static int memoization(int[] coins, int amount) {
    int[][] dp = new int[coins.length][amount + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    int res = memo(coins.length - 1, amount, coins, dp);
    return res >= INF ? -1 : res;
}

static int memo(int i, int t, int[] coins, int[][] dp) {
    if (i == 0) return t % coins[0] == 0 ? t / coins[0] : INF;
    if (dp[i][t] != -1) return dp[i][t];
    int notTake = memo(i - 1, t, coins, dp);
    int take = coins[i] <= t ? 1 + memo(i, t - coins[i], coins, dp) : INF;
    return dp[i][t] = Math.min(notTake, take);
}

Complexity. Time O(n · amount). Space O(n · amount) plus a stack that can be O(amount) deep. With a coin of value 1 and amount = 10^4, that is ten thousand nested calls, which may overflow Java’s default stack; the next two approaches have no such risk.

Approach 3: Tabulation

Intuition. dp[i][t] depends on dp[i - 1][t] (the row above) and dp[i][t - coins[i]] (the same row, further left). So fill row by row, and within a row from t = 0 upward; the cell to the left is then already final. Row 0 comes from the base case.

Compare with 0/1 problems, where “take” reads dp[i - 1][t - x], the row above. Reading the current row is the entire difference between “each item once” and “each item any number of times”.

Algorithm.

  1. Row 0: dp[0][t] = t / coins[0] if divisible, else INF.
  2. For i ≥ 1, t from 0 to amount: dp[i][t] = min(dp[i - 1][t], 1 + dp[i][t - coins[i]]), the second term only if coins[i] ≤ t.
  3. Return dp[n - 1][amount], or -1 if it is INF.
static int tabulation(int[] coins, int amount) {
    int n = coins.length;
    int[][] dp = new int[n][amount + 1];
    for (int t = 0; t <= amount; t++) dp[0][t] = t % coins[0] == 0 ? t / coins[0] : INF;
    for (int i = 1; i < n; i++) {
        for (int t = 0; t <= amount; t++) {
            int notTake = dp[i - 1][t];
            int take = coins[i] <= t ? 1 + dp[i][t - coins[i]] : INF;  // same row: coin i may be used again
            dp[i][t] = Math.min(notTake, take);
        }
    }
    return dp[n - 1][amount] >= INF ? -1 : dp[n - 1][amount];
}

Complexity. Time O(n · amount), space O(n · amount).

Approach 4: Space optimized

Intuition. Collapse the rows into one array best. Before processing coin c, best[t] holds the row above; processing t from left to right turns it into the current row, because best[t - c] has already been updated for c and so already allows copies of c. This is the opposite direction from the 0/1 subset problems, for exactly the reason described above.

We can also start from a cleaner base: best[0] = 0 and everything else INF means “with no coins at all, only 0 is reachable”; processing coins[0] first then reproduces row 0.

Algorithm.

  1. best[0] = 0, every other entry INF.
  2. For each coin c, for t from c to amount: best[t] = min(best[t], 1 + best[t - c]).
  3. Return best[amount], or -1 if it is INF.
static int spaceOptimized(int[] coins, int amount) {
    int[] best = new int[amount + 1];
    Arrays.fill(best, INF);
    best[0] = 0;                                                    // zero coins make amount 0
    for (int c : coins) {
        for (int t = c; t <= amount; t++) {                          // left to right: best[t - c] may already use c
            best[t] = Math.min(best[t], 1 + best[t - c]);
        }
    }
    return best[amount] >= INF ? -1 : best[amount];
}

Dry run on Example 1 (coins = [1, 2, 5], amount = 11), showing best[0..11] after each coin:

after coin best[0..11]
1 0 1 2 3 4 5 6 7 8 9 10 11
2 0 1 1 2 2 3 3 4 4 5 5 6
5 0 1 1 2 2 1 2 2 3 3 2 3

best[11] = 3, achieved as best[6] + 1 with best[6] = 2 (5 + 1), so the coins are 5 + 5 + 1.

Complexity. Time O(n · amount), space O(amount).

Edge cases and pitfalls