Knowledge Guide
Home › DSA › Dynamic Programming

Solution Minimum Coin Change

Introduction

Given an infinite supply of ‘n’ coin denominations and a total money amount, we are asked to find the minimum number of coins needed to make up that amount.

Example 1:

Denominations: {1,2,3}
Total amount: 5
Output: 2
Explanation: We need a minimum of two coins {2,3} to make a total of '5'

Example 2:

Denominations: {1,2,3}
Total amount: 11
Output: 4
Explanation: We need a minimum of four coins {2,3,3,3} to make a total of '11'

Problem Statement

Given a number array to represent different coin denominations and a total amount 'T', we need to find the minimum number of coins needed to make a change for 'T'. We can assume an infinite supply of coins, therefore, each coin can be chosen multiple times.

Constraints:

This problem follows the "Unbounded Knapsack" pattern.

Basic Solution

A basic brute-force solution could be to try all combinations of the given coins to select the ones that give a total sum of 'T'. This is what our algorithm will look like:

for each coin 'c' 
  create a new set which includes one quantity of coin 'c' if it does not exceed 'T', and 
     recursively call to process all coins 
  create a new set without coin 'c', and recursively call to process the remaining coins 
return the count of coins from the above two sets with a smaller number of coins

Code

Here is the code for the brute-force solution:

java
class Solution {

  public int countChange(int[] denominations, int total) {
    int result = this.countChangeRecursive(denominations, total, 0);
    return (result == Integer.MAX_VALUE ? -1 : result);
  }

  private int countChangeRecursive(
    int[] denominations,
    int total,
    int currentIndex
  ) {
    // base check
    if (total == 0) return 0;

    if (
      denominations.length == 0 || currentIndex >= denominations.length
    ) return Integer.MAX_VALUE;

    // recursive call after selecting the coin at the currentIndex
    // if the coin at currentIndex exceeds the total, we shouldn't process this
    int count1 = Integer.MAX_VALUE;
    if (denominations[currentIndex] <= total) {
      int res = countChangeRecursive(
        denominations,
        total - denominations[currentIndex],
        currentIndex
      );
      if (res != Integer.MAX_VALUE) {
        count1 = res + 1;
      }
    }

    // recursive call after excluding the coin at the currentIndex
    int count2 = countChangeRecursive(denominations, total, currentIndex + 1);

    return Math.min(count1, count2);
  }

  public static void main(String[] args) {
    Solution cc = new Solution();
    int[] denominations = { 1, 2, 3 };
    System.out.println(cc.countChange(denominations, 5));
    System.out.println(cc.countChange(denominations, 11));
    System.out.println(cc.countChange(denominations, 7));
    denominations = new int[] { 3, 5 };
    System.out.println(cc.countChange(denominations, 7));
  }
}

The time complexity of the above algorithm is exponential , where 'C' represents total coin denominations and 'T' is the total amount that we want to make change. The space complexity will be .

Let's try to find a better solution.

Top-down Dynamic Programming with Memoization

We can use memoization to overcome the overlapping sub-problems. We will be using a two-dimensional array to store the results of solved sub-problems. As mentioned above, we need to store results for every coin combination and for every possible sum:

java
class Solution {

  public int countChange(int[] denominations, int total) {
    Integer[][] dp = new Integer[denominations.length][total + 1];
    int result = this.countChangeRecursive(dp, denominations, total, 0);
    return (result == Integer.MAX_VALUE ? -1 : result);
  }

  private int countChangeRecursive(Integer[][] dp, int[] denominations, int total, int currentIndex) {
    // base check
    if (total == 0)
      return 0;

    if(denominations.length == 0 || currentIndex >= denominations.length)
      return Integer.MAX_VALUE;

    // check if we have not already processed a similar sub-problem
    if(dp[currentIndex][total] == null) {
      // recursive call after selecting the coin at the currentIndex
      // if the coin at currentIndex exceeds the total, we shouldn't process this
      int count1 = Integer.MAX_VALUE;
      if( denominations[currentIndex] <= total ) {
        int res = countChangeRecursive(dp, denominations, total - denominations[currentIndex], currentIndex);
        if(res != Integer.MAX_VALUE){
          count1 = res + 1;
        }
      }

      // recursive call after excluding the coin at the currentIndex
      int count2 = countChangeRecursive(dp, denominations, total, currentIndex + 1);
      dp[currentIndex][total] = Math.min(count1, count2);
    }
    return dp[currentIndex][total];
  }

  public static void main(String[] args) {
    Solution cc = new Solution();
    int[] denominations = {1, 2, 3};
    System.out.println(cc.countChange(denominations, 5));
    System.out.println(cc.countChange(denominations, 11));
    System.out.println(cc.countChange(denominations, 7));
    denominations = new int[]{3, 5};
    System.out.println(cc.countChange(denominations, 7));
  }
}

Bottom-up Dynamic Programming

Let's try to populate our array dp[TotalDenominations][Total+1] for every possible total with a minimum number of coins needed.

So for every possible total ‘t’ (0<= t <= Total) and for every possible coin index (0 <= index < denominations.length), we have two options:

Finally, we will take the minimum of the above two values for our solution:

    dp[index][t] = min(dp[index-1][t], dp[index][t-denominations[index]] + 1)

Let’s draw this visually with the following example:

    Denominations: [1, 2, 3]  
    Total: 7

Let’s start with our base case of zero total:

We don't need any coin to make zero total
We don't need any coin to make zero total
Total:1, Index:0 => dp[Index][Total-denominations[Index] + 1, we didn't consider dp[Index-1][Total] as Index = 0
Total:1, Index:0 => dp[Index][Total-denominations[Index] + 1, we didn't consider dp[Index-1][Total] as Index = 0
Total:2, Index:0 => dp[Index][Total-denominations[Index] + 1, we didn't consider dp[Index-1][Total] as Index = 0
Total:2, Index:0 => dp[Index][Total-denominations[Index] + 1, we didn't consider dp[Index-1][Total] as Index = 0
Total:3-7, Index:0 => dp[Index][Total-denominations[Index] + 1, we didn't consider dp[Index-1][Total] as Index = 0
Total:3-7, Index:0 => dp[Index][Total-denominations[Index] + 1, we didn't consider dp[Index-1][Total] as Index = 0
Total:1, Index:1 => dp[Index-1][t], we didn't consider dp[Index][Total-denominations[Index] as Total < denominations[Index]
Total:1, Index:1 => dp[Index-1][t], we didn't consider dp[Index][Total-denominations[Index] as Total < denominations[Index]
Total:2, Index:1 => min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)
Total:2, Index:1 => min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)
Total:3, Index:1 => min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)
Total:3, Index:1 => min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)
Total:4-7, Index:1 => min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)
Total:4-7, Index:1 => min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)
Total:7, Index:2 => min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)
Total:7, Index:2 => min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)

Code

Here is the code for our bottom-up dynamic programming approach:

java
import java.util.Arrays;

class Solution {

  public int countChange(int[] denominations, int total) {
    int n = denominations.length;
    int[][] dp = new int[n][total + 1];

    for (int i = 0; i < n; i++) for (int j = 0; j <= total; j++) dp[i][j] =
      Integer.MAX_VALUE;

    // populate the total=0 columns, as we don't need any coin to make zero total
    for (int i = 0; i < n; i++) dp[i][0] = 0;

    for (int i = 0; i < n; i++) {
      for (int t = 1; t <= total; t++) {
        if (i > 0) dp[i][t] = dp[i - 1][t]; //exclude the coin
        if (t >= denominations[i]) {
          if (dp[i][t - denominations[i]] != Integer.MAX_VALUE) dp[i][t] =
            Math.min(dp[i][t], dp[i][t - denominations[i]] + 1); // include the coin
        }
      }
    }

    // total combinations will be at the bottom-right corner.
    return (dp[n - 1][total] == Integer.MAX_VALUE ? -1 : dp[n - 1][total]);
  }

  public static void main(String[] args) {
    Solution cc = new Solution();
    int[] denominations = { 1, 2, 3 };
    System.out.println(cc.countChange(denominations, 5));
    System.out.println(cc.countChange(denominations, 11));
    System.out.println(cc.countChange(denominations, 7));
    denominations = new int[] { 3, 5 };
    System.out.println(cc.countChange(denominations, 7));
  }
}

The above solution has time and space complexity of , where 'C' represents total coin denominations and 'T' is the total amount that we want to make change.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Minimum Coin Change? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Minimum Coin Change** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Minimum Coin Change** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Minimum Coin Change**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Minimum Coin Change**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Coin ChangeSolution Maximum Ribbon Cut →