Back to DSA
Coin Change
mediumYou have coins of various denominations available in unlimited supply. Determine the minimum number of coins required to reach a specified total. If the total cannot be assembled from the given denominations, return -1.
Examples
Example 1:
Input:
coins = [1,3,4], amount = 6Output:
2Explanation: 6 = 3 + 3, using two coins.
Example 2:
Input:
coins = [5,7], amount = 3Output:
-1Explanation: No combination of 5s and 7s can produce 3.
Hints
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
java.util.Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}Time complexity
O(amount * n)Space complexity
O(amount)