Problem
1. 题目简述
给出一些面值的硬币coins，和目标金额mount，找出最少需要多少枚硬币能够组成amount，如果无法组成，则返回-1。例如：
Example 1：
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
2. 算法思路
相关问题：
经典老题目，我们需要留意的是它和combination sum的区别，combination sum是找具体的组合，而coin change只要找最小的合法组合。因此，这道题我们考虑用dp，而不是回溯法。
那么如何找到最优子问题呢？对于例子中的amount为11，它有几种组合方式：（1）10 + 1 （2）9 + 2 （3）6 + 5，找出这三者中最小的即可。其base case是当amount为0的时候，组合方式有且只有一种。递推式如下：
$$dp[i] = Math.min(dp[i - coin] + 1, dp[i]) (for coin in coins)$$
动态规划（top-down）
初始化的值没必要设置成Integer.MAX_VALUE，最大设置为amount+1即可，因为最多也就是amount个1元硬币。
class Solution {
// 注意和combination sum的区别，combination sum是要找所有的解决方案，所以采用回溯，这里只要找最少的那个就好了。
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
return getMinCoins(coins, amount, dp, amount + 1);
}
private int getMinCoins(int[] coins, int amount, int[] dp, int max) {
if (amount < 0) {
return -1;
} else if (amount == 0) {
return 0;
}
if (dp[amount] != 0) {
return dp[amount];
}
// 这里不用min，直接用dp[amount]直接操作也可以的！！！
// dp[amount] = max + 1;
// for (int coin : coins) {
// int temp = getMinCoins(coins, amount - coin, dp, max);
// dp[amount] = temp == -1 ? dp[amount] : Math.min(dp[amount], temp + 1);
// }
//dp[amount] = dp[amount] == max + 1 ? -1 : dp[amount];
int min = max + 1;
for (int coin : coins) {
int temp = getMinCoins(coins, amount - coin, dp, max);
min = temp == -1 ? min : Math.min(min, temp + 1);
}
dp[amount] = min == max + 1 ? -1 : min;
return dp[amount];
}
}动态规划（Bottom-up）
这里我们需要注意的只有边界case，也就是dp[0] = 0，这里要和coin change 2进行区分，那个是求方式，这个是求硬币数，不一样的！！！
class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] >= max ? -1 : dp[amount];
}
}