題目

他會給我一個整數陣列coins[]，代表的就是各個硬幣的面額，然後還會給我們一個數字amount，我們要做的就是用他給的面額湊出那個數字，而且湊出來的硬幣數要最少，而回傳的東西則是我們湊出來數字的最少硬幣數。

想法

我先想說我可以每個硬幣都試試看，然後我用dp[i]來表示湊出i最少的硬幣數，然後跟當小偷偷錢那題很像，只是我們現在要的是最少的那一個。
那我是從最小的開始試，然後一直往上算，如果i-coin>=0就表示我可以用這個硬幣，然後再去dp[]裡面找i-coin最少要幾個硬幣最後記得加上我們剛剛前面先扣的硬幣(+1)，再比較看看這個方法是不是有更少的硬幣數。
然後如果都湊不出來要回傳-1。
阿如果amount=0的話就是dp[0]=0

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0; // 0元要0枚

        for (int i = 1; i <= amount; i++) {

            //嘗試每一種硬幣
            for (int j = 0; j < coins.length; j++) {
                int coin = coins[j];
                if (i - coin >= 0) { // 如果這個硬幣可以
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] ;
    }
}

這是我一開始自己寫的，然後執行之後他跑出Wrong Answer

後來我就丟去問gpt為甚麼會這樣，他跟我說因為我沒有假設到湊不出來這個情況發生怎麼辦，所以他又幫我加了兩行東西。

Arrays.fill(dp, amount + 1);

這的意思就是因為我一開始不知道怎麼湊，所以幫整個dp陣列填入了一個超級大的數字，用來表示一開始全部的金額都湊不出來，就是比amount大的數字，那就是amount+1了，之後如果有比他小的就會跟他比較然後被加進來。

return dp[amount] == amount + 1 ? -1 : dp[amount];

這代表如果我們要回傳的值如果是amount+1的話就表示這個數沒被湊出來，那他就會回傳-1，不然就回傳dp[amount]

程式碼

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // 先假設都湊不出來
        dp[0] = 0; // 0元要0枚

        for (int i = 1; i <= amount; i++) {
            //試每一種硬幣
            for (int j = 0; j < coins.length; j++) {
                int coin = coins[j];
                if (i - coin >= 0) { //如果可以用這個硬幣
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        //如果最後還是amount+1，代表湊不出來
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

執行成功