有点类似 perfect squares那道题-279.
public class Solution {
public int coinChange(int[] coins, int amount) {
int dp[] = new int[amount+1];
for (int i=1; i<=amount; i++) {
int min_tmp = Integer.MAX_VALUE;
for (int j=0; j<coins.length; j++) {
// if the amount can be found in the coins array;
if(i == coins[j]) {
min_tmp = 1;
break;
// if cannot be found, but can keep on minus the coins value;
} else if (i > coins[j] && dp[i-coins[j]] > 0 && dp[i-coins[j]]+1 < min_tmp)
min_tmp = dp[i-coins[j]]+1;
}
dp[i] = min_tmp == Integer.MAX_VALUE ? -1 : min_tmp;
}
return dp[amount];
}
}
