332.零錢兌換

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。計算并返回可以湊成總金額所需的 最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。你可以認為每種硬幣的數量是無限的。

輸入：數組，目標錢
輸出：零錢數量
思路：使用動態規劃

class Solution {public int coinChange(int[] coins, int amount) {int[] f = new int[amount + 1];f[0] = 0;for(int i = 1; i <= amount; i++){int minNum = Integer.MAX_VALUE;for(int j = 0; j < coins.length; j++){if(i - coins[j] >= 0 && f[i - coins[j]] < minNum){minNum = f[i - coins[j]] + 1;}}f[i] = minNum;}return f[amount] == Integer.MAX_VALUE ? -1 : f[amount];}
}

另外一種寫法

class Solution {public int coinChange(int[] coins, int amount) {int[] f = new int[amount + 1];Arrays.fill(f, amount + 1);f[0] = 0;for(int i = 1; i <= amount; i++){for(int j = 0; j < coins.length; j++){if(i - coins[j] >= 0 ){f[i] = Math.min(f[i], f[i - coins[j]] + 1);}}}return f[amount] == (amount + 1) ? -1 : f[amount];}
}