題目
#

題目簡述
#

給定不同面額的硬幣 coins 和一個總金額 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
Explanation: 無法用面額為 2 的硬幣湊出金額 3。

Example 3:

Input: coins = [1], amount = 0
Output: 0
Explanation: 金額為 0 時不需要任何硬幣。

解題思路
#

這題要求我們找出湊出指定金額所需的最少硬幣數量。如果無法湊出該金額，則返回 -1。

解法
#

使用 dp 陣列，dp[i] 表示湊出金額 i 所需的最少硬幣數量
初始化 dp[0] = 0，其他位置設為 Integer.MAX_VALUE（表示無法湊出）
對於每個金額 i，嘗試使用每種硬幣面額
如果可以使用某種硬幣，使用 Math.min() 更新 dp[i] 為最小值
最後檢查如果 dp[amount] 仍為 Integer.MAX_VALUE，則返回 -1

對於金額 i，我們可以嘗試使用每種硬幣面額 coins[j]
如果 i >= coins[j] 且 dp[i-coins[j]] != Integer.MAX_VALUE，則可以使用該硬幣
dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1)
最終檢查 dp[amount] 是否為 Integer.MAX_VALUE，如果是則返回 -1

例子說明
#

coins = [1,2,5], amount = 11

初始化：dp[0] = 0, dp[1...11] = Integer.MAX_VALUE

計算 dp[1]：
- 可以使用硬幣 1：dp[1] = Math.min(Integer.MAX_VALUE, dp[0] + 1) = 1
計算 dp[2]：
- 可以使用硬幣 1：dp[2] = Math.min(Integer.MAX_VALUE, dp[1] + 1) = 2
- 可以使用硬幣 2：dp[2] = Math.min(2, dp[0] + 1) = 1
- 取最小值：dp[2] = 1
計算 dp[3]：
- 可以使用硬幣 1：dp[3] = Math.min(Integer.MAX_VALUE, dp[2] + 1) = 2
- 可以使用硬幣 2：dp[3] = Math.min(2, dp[1] + 1) = 2
- 取最小值：dp[3] = 2
以此類推…
最終結果：
- dp[11] = 3（使用 5 + 5 + 1）

完整程式碼
#

java

import java.util.*;

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 創建dp陣列，dp[i]表示湊出金額i所需的最少硬幣數量
        int[] dp = new int[amount+1];

        // 初始化所有位置為Integer.MAX_VALUE，表示無法湊出
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 金額為0時不需要任何硬幣
        dp[0] = 0;
        
        // 遍歷每個金額，從1到amount
        for(int i = 1; i <= amount; i++){
            // 嘗試使用每種硬幣面額
            for(int j = 0; j < coins.length; j++){
                // 如果當前金額大於等於硬幣面額，且使用該硬幣後的剩餘金額可以湊出
                if(i >= coins[j] && dp[i-coins[j]] != Integer.MAX_VALUE){
                    // 使用Math.min()更新為使用當前硬幣的結果
                    dp[i] = Math.min(dp[i-coins[j]] + 1, dp[i]);
                }
            }
        }

        // 如果最終結果仍為Integer.MAX_VALUE，表示無法湊出目標金額，返回-1
        if(dp[amount] == Integer.MAX_VALUE){
            dp[amount] = -1;
        }

        // 返回湊出目標金額所需的最少硬幣數量
        return dp[amount];
    }
}