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

示例?1:

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

輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認為每種硬幣的數量是無限的。

分析：最后一句話說明是什么背包類型了，直接一頓敲

不會的翻我的動態規劃文章就行了。

public 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 j = 0; j < coins.length; j++) {if (coins[j] <= i) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}