
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:
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
.
- You need to make the exact total
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 toamount
. - Initialize
dp[0]
to0
because zero coins are needed to make the amount zero. - Set all other entries in
dp
to a large number (likeamount + 1
or some max value) initially, indicating those amounts can’t yet be reached by any combination of the coins.
- Create an array
Table Filling Logic:
- For each sub-amount
x
ranging from1
toamount
, and for each coin in your coins array:- If the coin denomination is less than or equal to
x
, updatedp[x]
to the minimum of its current value and1 + 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 valuex
if it's possible; otherwise, it remains at its initialized value.
- If the coin denomination is less than or equal to
- For each sub-amount
Result Extraction:
- If
dp[amount]
remains greater thanamount
(the initial placeholder), it implies there's no possible combination that totals up toamount
, hence return-1
. - Otherwise, the value at
dp[amount]
is the minimum number of coins needed to make up that amount.
- If
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
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 sizetotal + 1
to store the minimum number of coins needed for each sub-amount from 0 tototal
. 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 thecurrency
array. If the denomination is less than or equal to the sub-amounti
, it updatesdpTable[i]
to be the minimum of its current value and the value ofdpTable[i - currency[c]] + 1
.Finally, it checks if the value at
dpTable[total]
is still greater thantotal
(the initializedupperBound
). 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 ofdpTable[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
.
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
wherecache[i]
represents the minimum number of coins needed to achieve the valuei
. Initially, set all values in this list to infinity (float('inf')
), except forcache[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.
No comments yet.