import java.util.Arrays;
public class CoinChange {
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int[] dp = new int[amount + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin: coins) {
if (i - coin >= 0 && dp[i - coin] >= 0) {
int k = dp[i - coin] + 1;
dp[i] = dp[i] > 0 ? Math.min(dp[i], k) : k;
}
}
}
return dp[amount];
}
}