322-Coin Change
就是完全背包问题，可以再复习一遍背包问题。
01背包：
for 每一个item
for amount...cost[item]
f[v] = Max{f[v], f[v-cost[item]] + weight[item]}
因为01背包每个item只能用一次，所以amount要从后往前算，因为比较的时候用的是f[v]和f[v-cost[item]]，第二个那里是减号，所以退着算，后面的结果前面没有使用.
完全背包
for 每一个item
for cost[item]...amout
f[v] = Max{f[v], f[v-cost[item]] + weight[item]}
因为每一个物品可以用很多次，所以amount从小往大走，因为每一次后面的结果都用到了前面的结果。如果要求满背包，就把f[0]设置为0，其他都设置为Integer.MIN_VALUE.下面讨论本题，本题是一个完全背包问题，coins[]就是cost[], amount就是背包的容量，要求背包刚好装满，weight是所有的item都为1.区别是传统背包问题是要求最大weight，但是本题是求最小weight，所以在初始化上有区别。dp[0] = 0, 剩下的都是Integer.MAX_VALUE.
public int coinChange(int[] coins, int amount) {
if (coins.length == 0 || amount < 0) {
return -1;
}
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = coins.length - 1; i >= 0; i--) {
for (int j = coins[i]; j <= amount; j++) {
if (dp[j - coins[i]] != Integer.MAX_VALUE) {
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}