Coin Change

Updated on 13 May, 2025
Coin Change header image

Problem Statement

In this task, you work with an array of integers termed as coins, where each integer represents a particular coin denomination. Concurrently, you have an integer amount that signifies a specific total monetary value. The objective is to determine the minimum number of coins required to sum up to the amount. If it's not feasible to attain the amount using any permutations of the coins available, the function should return -1. This scenario operates under the assumption that there is an unlimited supply of each coin denomination represented in the array.

Examples

Example 1

Input:

coins = [1,2,5], amount = 11

Output:

3

Explanation:

11 = 5 + 5 + 1

Example 2

Input:

coins = [2], amount = 3

Output:

-1

Example 3

Input:

coins = [1], amount = 0

Output:

0

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

Approach and Intuition

In tackling the problem of finding the fewest number of coins needed for a given amount, a dynamic programming approach is highly effective. Below is a breakdown of the approach and the logic behind its application:

  1. Understanding the problem:

    • You need to make the exact total amount using the smallest number of coins from the given denominations.
    • An option where no coins make up the desired amount should return -1.
  2. Dynamic Programming Table Initialization:

    • Create an array dp where the length is amount + 1 to store the minimum number of coins needed to make each possible value up to amount.
    • Initialize dp[0] to 0 because zero coins are needed to make the amount zero.
    • Set all other entries in dp to a large number (like amount + 1 or some max value) initially, indicating those amounts can’t yet be reached by any combination of the coins.
  3. Table Filling Logic:

    • For each sub-amount x ranging from 1 to amount, and for each coin in your coins array:
      • If the coin denomination is less than or equal to x, update dp[x] to the minimum of its current value and 1 + dp[x - coin_value]. This represents either not using the current coin or using it and figuring out the minimum coins needed for the remainder (x - coin_value).
      • This updating ensures that the dp[x] will eventually hold the minimum coins required to make the value x if it's possible; otherwise, it remains at its initialized value.
  4. Result Extraction:

    • If dp[amount] remains greater than amount (the initial placeholder), it implies there's no possible combination that totals up to amount, hence return -1.
    • Otherwise, the value at dp[amount] is the minimum number of coins needed to make up that amount.

This approach leverages the concept that each sub-problem (i.e., minimum coins for smaller amounts) can contribute to a larger problem, reducing redundant calculations and ensuring that the solution is both time and space-efficient within the given constraints.

Solutions

  • Java
  • Python
java
public class Solution {
  public int minCoins(int[] currency, int total) {
    int upperBound = total + 1;
    int[] dpTable = new int[total + 1];
    Arrays.fill(dpTable, upperBound);
    dpTable[0] = 0;
    for (int i = 1; i <= total; i++) {
      for (int c = 0; c < currency.length; c++) {
        if (currency[c] <= i) {
          dpTable[i] = Math.min(dpTable[i], dpTable[i - currency[c]] + 1);
        }
      }
    }
    return dpTable[total] > total ? -1 : dpTable[total];
  }
}

The Java solution provided computes the minimum number of coins needed to make up a given amount, using the classical dynamic programming approach. The method, minCoins, accepts two parameters: an array currency containing the denominations of the coins available, and an integer total, which is the amount for which we need to find the minimum number of coins.

Here’s a concise breakdown of how the algorithm is structured:

  • Initializes an array dpTable of size total + 1 to store the minimum number of coins needed for each sub-amount from 0 to total. It fills this array with a value greater than any possible number of coins needed (upperBound), except for the first element, dpTable[0], which is set to 0 because no coins are needed to make an amount of 0.

  • Iterates over each sub-amount from 1 to total and for each denomination available in the currency array. If the denomination is less than or equal to the sub-amount i, it updates dpTable[i] to be the minimum of its current value and the value of dpTable[i - currency[c]] + 1.

  • Finally, it checks if the value at dpTable[total] is still greater than total (the initialized upperBound). If so, it means it is not possible to form the amount with the given coins, and it returns -1. Otherwise, it returns the value of dpTable[total], which represents the minimum number of coins.

This solution ensures efficient computation by avoiding unnecessary recalculations and by systematically building up the solution through the dpTable.

python
class Solution:
    def getMinCoins(self, denominations: List[int], total: int) -> int:
        cache = [float('inf')] * (total + 1)
        cache[0] = 0

        for denomination in denominations:
            for i in range(denomination, total + 1):
                cache[i] = min(cache[i], cache[i - denomination] + 1)
        return cache[total] if cache[total] != float('inf') else -1

The Coin Change algorithm in Python3 involves determining the minimum number of coins needed to make up a specific amount using given denominations. Here's how the solution works:

  • Initialize a list cache where cache[i] represents the minimum number of coins needed to achieve the value i. Initially, set all values in this list to infinity (float('inf')), except for cache[0] which is 0 because no coins are needed to make up the amount 0.

  • Loop through each coin denomination. For each denomination, iterate through possible totals from the denomination value up to the desired total. Update the cache list by comparing the existing value with the new possible minimum number of coins needed (either keep it the same or take the denomination and add one to the number of coins needed to make up the total minus the denomination).

  • Finally, if cache[total] holds a value other than infinity, it contains the minimum number of coins required for the given total, otherwise return -1, signaling that it's not possible to sum to the total with the provided denominations.

This dynamic programming approach ensures that each sub-problem is solved efficiently and results can be reused, leading to an overall efficient solution for the minimum coin change problem.

Comments

No comments yet.