322. Coin Change

📘 題目敘述

給定一個整數陣列 coins 表示不同面額的硬幣，以及一個整數 amount 表示總金額。

請回傳「湊出 amount 所需的最少硬幣數量」。如果無法湊出剛好 amount，則回傳 -1。

條件限制

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

🧠 解題思路

我的核心想法是記錄每個金額目前已知的最少硬幣數，再從 0 開始往外擴展：

• 我把「每個金額 now」都記一個目前已知的最少硬幣數 better[now]
• 從 now = 0 開始，用遞迴去嘗試「再加一枚硬幣」能到達哪些新金額
• 只要我找到某個金額 now 的更好解（tol 更小），我才繼續往外擴展
• 這樣就能剪掉很多「已經比目前更差」的走法

直覺上，它很像在做一種「狀態擴展」：狀態是金額 now，邊是「加上一個硬幣面額」，成本是 +1 枚硬幣；我只保留每個狀態目前最好的成本。

所有變數

better

• better[x] 代表目前我已經找到的「湊到金額 x 的最少硬幣數」
• 一開始全部設成很大（20000），表示「還沒找到方法」

coin

• 我把 coins 裡面 <= amount 的面額存進來（大於 amount 的面額加了也沒意義）

charge(now, tol, amo)

• now：目前湊到的金額
• tol：目前用了幾枚硬幣（total coins）
• amo：目標金額（amount）

🪜 主要流程步驟

1) 初始化 better

• 我先把 better 建成長度 amount + 1
• 每個位置先放 20000（代表「目前還不知道最少幾枚」）

2) 過濾硬幣面額

• 我只把 <= amount 的硬幣放進 coin
• 因為如果面額比 amount 大，從 0 開始加它永遠不可能剛好幫到 amount

3) 從 0 開始遞迴擴展：charge(0, 0, amount)

在 charge 裡面，我的判斷順序是：

情況一：now > amo

• 超過目標金額，這條路直接停止（不再往下加）

情況二：tol < better[now]

• 代表我「找到一個更省硬幣的方式」到達 now
• 我會更新 better[now] = tol
• 然後再嘗試把每一種硬幣加上去，去探索 now + coin[i]

情況三：tol >= better[now]

• 代表這次走到 now 的方法不夠好（硬幣數沒比較少）
• 那我就不繼續往下展開，因為只會更差（硬幣數只會越加越多）

4) 最後回傳答案

• 如果 better[amount] 還是 20000：表示根本沒有任何方法能湊到 amount → 回傳 -1
• 否則回傳 better[amount]

💻 程式碼實作

class Solution {
public:
    vector<int> better;
    vector<int> coin;

    void charge(int now, int tol, int amo) {
        if (now <= amo) {
            if (tol < better[now]) {
                better[now] = tol;
                for (int i = 0; i < coin.size(); i++) {
                    charge(now + coin[i], tol + 1, amo);
                }
            }
        }
    }

    int coinChange(vector<int>& coins, int amount) {
        better.assign(amount + 1, 20000);
        for (int a : coins) {
            if (a <= amount) {
                coin.push_back(a);
            }
        }
        charge(0, 0, amount);
        return (better[amount] == 20000 ? -1 : better[amount]);
    }
};

🔗 題目連結

https://leetcode.com/problems/coin-change/