public int coinChange(int[] coins, int amount) {

if (coins == null || coins.length == 0) {

return -1;

}

int[] dp = new int[amount + 1];

dp[0] = 0;

for (int i = 1; i <= amount; i++) {

dp[i] = Integer.MAX_VALUE;

for (int coin : coins) {

if (i >= coin && dp[i - coin] != -1 && coin != 0) {

dp[i] = Math.min(dp[i], dp[i - coin] + 1);

}

}

if (dp[i] == Integer.MAX_VALUE) {

dp[i] = -1;

}

}

return dp[amount];

}

int[] dp;

public int coinChange(int[] coins, int amount) {

if (coins == null || coins.length == 0) {

return -1;

}

dp = new int[amount + 1];

for (int i = 1; i <= amount; i++) {

dp[i] = Integer.MAX_VALUE;

}

return dfs(coins, amount);

}

private int dfs(int[] coins, int amount) {

if (amount < 0) {

return -1;

}

if (dp[amount] != Integer.MAX_VALUE) {

return dp[amount];

}

for (int coin : coins) {

int temp = dfs(coins, amount - coin);

if (temp >= 0) {

dp[amount] = Math.min(dp[amount], temp + 1);

}

}

return dp[amount] = dp[amount] == Integer.MAX_VALUE ? - 1 : dp[amount];

}

public int coinChange(int[] coins, int amount) {

if (coins == null || coins.length == 0) {

return -1;

}

final int[] dp = new int[amount + 1];

dp[0] = 0;

for (int i = 1; i < dp.length; i++) { // 1: 1, 2: 2, 5

dp[i] = -1;

for (int coin : coins) {

if (i >= coin && dp[i - coin] != -1) {

if (dp[i] == -1 || dp[i - coin] + 1 < dp[i]) {

dp[i] = dp[i - coin] + 1;

}

}

}

}

return dp[amount];

}