package array.iterative;
import java.util.Arrays;
public class CoinChange {
public int coinChange(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, Integer.MAX_VALUE);
memo[0] = 0;
for (int i = 1; i < memo.length; i++)
for (var coin : coins) {
if (i - coin < 0 || memo[i - coin] == Integer.MAX_VALUE) continue;
memo[i] = Math.min(memo[i], memo[i - coin] + 1);
}
return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
}
}
package array.recursive;
public class CoinChange {
public int coinChange(int[] coins, int amount) {
int coinChange = dfs(coins, amount, new Integer[amount + 1]);
return coinChange == Integer.MAX_VALUE ? -1 : coinChange;
}
private int dfs(int[] coins, int amount, Integer[] memo) {
if (amount == 0)
return 0;
if (memo[amount] != null)
return memo[amount];
int minCoinChange = Integer.MAX_VALUE;
for (var coin : coins) {
if (amount - coin < 0) continue;
int coinChange = dfs(coins, amount - coin, memo);
if (coinChange == Integer.MAX_VALUE) continue;
minCoinChange = Math.min(minCoinChange, coinChange + 1);
}
return memo[amount] = minCoinChange;
}
}