经典动态规划背包问题，dp[i][j]表示用前i种硬币能达到金额j的最小硬币数量。
这里是一个讲解很好的视频。
Time = O(n*amount), space = O(amount)
class Solution {
public int coinChange(int[] coins, int amount) {
int[] numOfCoins = new int[amount + 1];
numOfCoins[0] = 0;
for (int i = 1; i < numOfCoins.length; i++) {
numOfCoins[i] = Integer.MAX_VALUE - 1;
}
for (int i = 0; i < coins.length; i++) {
for (int j = 1; j <= amount; j++) {
if (coins[i] <= j) {
numOfCoins[j] = Math.min(numOfCoins[j], 1 + numOfCoins[j - coins[i]]);
}
}
}
return numOfCoins[amount] > amount ? -1 : numOfCoins[amount];
}
}