Problem
You are given an array of coin denominationscoins and an integer amount.
Return the minimum number of coins required to make the given amount. If the amount cannot be made using the available coins, return
-1.
You may use each coin denomination any number of times.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
coins = [1,2,5]
amount = 11Output
3Solution
This problem can be solved using Memoization.Think about the remaining amount. For each available coin, we choose that coin and recursively calculate the minimum number of coins needed for the remaining amount.
If the remaining amount becomes
0, we have successfully formed the required amount, so no more coins are needed.
If the remaining amount becomes negative, that combination is invalid, so we return
-1.
For every remaining amount, we try all available coins. If choosing a coin leads to a valid solution, we add
1 for the current coin and keep the minimum result.
The same remaining amount can be reached through different combinations of coins. Therefore, we store previously calculated results in a memoization array.
class Solution {
public int coinChange(int[] coins, int amount) {
Integer[] memo = new Integer[amount + 1];
return coinChangeHelper(coins, amount, memo);
}
private int coinChangeHelper(int[] coins, int amount, Integer[] memo) {
// Amount reached, no more coins needed
if (amount == 0)
return 0;
// Invalid amount
if (amount < 0)
return -1;
// Return already calculated result
if (memo[amount] != null)
return memo[amount];
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeHelper(coins, amount - coin, memo);
if (result >= 0)
min = Math.min(min, result + 1);
}
// No valid combination found
return memo[amount] = min == Integer.MAX_VALUE ? -1 : min;
}
}
Complexity
There are at mostamount different remaining amounts. For each amount, we try every available coin. Therefore, the time complexity is O(amount × coins.length).
The memoization array requires
O(amount) space, and the recursion stack can grow up to O(amount).
Tabulation Approach
Instead of recursively solving smaller amounts, we can build the solution from0 up to the target amount.
Let
dp[i] represent the minimum number of coins required to make amount i. The base case is:
dp[0] = 0dp[i] = min(dp[i], dp[i - coin] + 1)
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// Mark all amounts as initially unreachable.
Arrays.fill(dp, amount + 1);
// Zero coins are needed to make amount 0.
dp[0] = 0;
for (int current = 1; current <= amount; current++) {
for (int coin : coins) {
if (coin <= current) {
dp[current] = Math.min(
dp[current],
dp[current - coin] + 1
);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
Complexity
For each amount from1 to amount, we try every coin denomination, resulting in O(amount × coins.length) time complexity.
The DP array requires
O(amount) space.