331，零錢兌換

給定不同面額的硬币 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬币個數。如果沒有任何一種硬币組合能組成總金額，傳回 -1。

示例 1:

輸入: coins = [1, 2, 5], amount = 11
輸出: 3 
解釋: 11 = 5 + 5 + 1      

示例 2:

輸入: coins = [2], amount = 3
輸出: -1      

答案：

1public int coinChange(int[] coins, int amount) {
 2    int Max = amount + 1;
 3    int[] dp = new int[amount + 1];
 4    Arrays.fill(dp, Max);
 5    dp[0] = 0;
 6    for (int i = 1; i <= amount; i++) {
 7        for (int j = 0; j < coins.length; j++) {
 8            if (coins[j] <= i) {
 9                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
10            }
11        }
12    }
13    return dp[amount] > amount ? -1 : dp[amount];
14}      

解析：

看到這題我們首先想到的是動态規劃，很類似于背包問題，就是目前硬币有選和不選兩種狀态，哪種情況下得到的硬币是最少的，對動态規劃比較熟悉的話這題就比較容易了解了，我們還以上面的資料畫個圖就更容易了解了

1public int coinChange(int[] coins, int amount) {
 2    if (amount < 1)
 3        return 0;
 4    return helper(coins, amount, new int[amount]);
 5}
 6
 7private int helper(int[] coins, int rem, int[] count) {
 8    if (rem < 0)
 9        return -1; // 無效
10    if (rem == 0)
11        return 0; // 計算完成了
12    if (count[rem - 1] != 0)
13        return count[rem - 1]; // 已經計算過了
14    int min = Integer.MAX_VALUE;
15    for (int coin : coins) {
16        int res = helper(coins, rem - coin, count);
17        if (res >= 0 && res < min)
18            min = 1 + res;
19    }
20    count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
21    return count[rem - 1];
22}