###### tags: `APCS`
# **d904_v2－換零錢**
### **題目連結：** [**d904**](https://zerojudge.tw/ShowProblem?problemid=d904)
### **題目解析**
這題的問題是經典的「找零問題」（Coin Change Problem），要求你使用最少數量的硬幣來湊出特定的金額。題目給定N種不同面額的硬幣，以及需要湊出的總金額C，目標是找出所需的最少硬幣數量。
### **解題方向**
這類問題通常可以用動態規劃（Dynamic Programming）來解決。動態規劃的基本思想是將問題分解為一系列子問題，並利用這些子問題的解來構建原問題的解。
1. 問題轉化：
* 我們要找出如何用最少數量的硬幣來湊出`C`美分。
* 定義一個數組`method[i]`，其值代表湊出`i`美分所需的最少硬幣數量。
1. 狀態轉移：
* 對於每一種硬幣面額`coin[k]`，如果我們已經知道湊出`j - coin[k]`美分的最少硬幣數量，那麼我們可以嘗試使用這枚硬幣來湊出j美分。
* `method[j]`可以透過比較當前的值和`method[j - coin[k]] + 1`來得到最小值。
1. 初始條件：
* 當金額為`0`時，所需的硬幣數量是`0`，即`method[0] = 0`。
* 對於其他金額，初始時設為一個很大的數字（如100000），表示還沒有找到有效的硬幣組合。
1. 結果輸出：
* 當所有計算完成後，`method[C]`就是湊出`C`美分所需的最少硬幣數。
### **程式解析**
1. 初始化：
* `method[]`陣列的大小是`C+1`，所有值初始化為`100000`（表示初始無法湊出）。
* `method[0]`設為`0`，因為湊出`0`美分不需要任何硬幣。
1. 動態規劃迴圈：
* 第一個迴圈遍歷所有的硬幣種類，第二個迴圈計算從當前硬幣面額到總金額`C`的最少硬幣數量。
* 在每次迴圈內，根據已知的結果（湊出`j - coin[i]`的最少硬幣數量），計算湊出金額`j`所需的最少硬幣數。
1. 結果輸出：
* 最後的結果存儲在`method[C]`中，表示湊出`C`美分所需的最少硬幣數量。
### **完整程式碼**

# 讀取輸入
s = input()
C, N = map(int, s.split())

coin = []
method = [100000 for _ in range(C+1)]  # 初始化method數組，設為一個大數

for i in range(N):
    coin.append(int(input()))  # 讀取所有硬幣面額

method[0] = 0  # 初始化method[0] 為 0，因為湊出 0 美分不需要硬幣

# 動態規劃的核心部分
for i in range(N):  # 遍歷每種硬幣
    for j in range(coin[i], C+1):  # 遍歷從當前硬幣面額到C的所有金額
        if method[j] > method[j - coin[i]] + 1:  # 如果使用當前硬幣可以使硬幣數量更少
            method[j] = method[j - coin[i]] + 1  # 更新最少硬幣數量

print(method[C])  # 輸出湊出C美分所需的最少硬幣數量

### **補充說明**
C = 6 （目標金額為6美分）
N = 3 （有3種不同的硬幣）
硬幣面值 = [1, 3, 4]

1. **初始化**：
- 將`method[0]`設為0，因為組成0美分需要0個硬幣。
- 將`method[1]`至`method[6]`初始化為100000，作為一個很大的數值，表示尚未找到更好的解。
2. **開始處理每種硬幣**：
- 對於第一種硬幣（1美分）：
- **`j`** 從1循環到6。
- 每次循環時，將`method[j]`**與**`method[j - coin[i]] + 1`**進行比較。由於**`coin[i]`**此時為1，這意味著每個**`method[j]`**將與**`method[j - 1] + 1`比較。
- 例如，當`j = 1`時，**`method[1]`**（初始為100000）將與`method[0] + 1`**（即1）進行比較，顯然1更小，因此**`method[1]`**更新為1。這一過程將持續下去，導致**`method[1]`**至**`method[6]`分別更新為1, 2, 3, 4, 5, 6。
- 對於第二種硬幣（3美分）：
- **`j`** 從3循環到6。
- 當`j = 3`時，**`method[3]`**（此時為3，使用了三個1美分硬幣）將與`method[3-3] + 1`**（即**`method[0]+1=1`**，表示使用一個3美分硬幣）進行比較。因為1<3，所以**`method[3]`更新為1。
- 當`j = 4`**時，**`method[4]`**（此時為4，使用了四個1美分硬幣）將與**`method[4-3] + 1`**（即**`method[1]+1=2`**，表示使用一個3美分硬幣加上一個1美分硬幣）進行比較。因為2<4，所以**`method[4]`更新為2。
- 當`j = 5`**和**`j = 6`**時，類似地更新**`method[5]`**為3（使用一個3美分和二個1美分硬幣）和**`method[6]`為2（使用兩個3美分硬幣）。
- 對於第三種硬幣（4美分）：
- **`j`** 從4循環到6。
- 當`j = 4`**時，**`method[4]`**已經是2，使用一個3美分和一個1美分硬幣。**`method[4-4]+1`**（即**`method[0]+1=1`**，表示使用一個4美分硬幣）更小，所以**`method[4]`更新為1。
- 當`j = 5`時，改為用2個硬幣（原本是3個）。
- 對於 `j = 6`，更新過程繼續，但由於`method[6]`已經是最小（2個硬幣），所以它不會再有更新。
3. **輸出結果**：程式最後輸出`method[C]`**的值，即組成C美分（在此例中為6美分）所需的最少硬幣數。在此例中，**`method[6]`的值可能是2，表示最少需要兩個硬幣來達成目標金額。這兩個硬幣的組合可能是兩個3美分的硬幣，或者一個4美分加上兩個1美分的硬幣。
4. 額外補充：

當我們看到 **`method[j - coin[i]] + 1`**：

- **`j - coin[i]`** 表示從當前目標金額 **`j`** 中扣除一個 **`coin[i]`** 面值的硬幣後，剩下需要組成的金額。
- **`method[j - coin[i]]`** 就是組成這個剩餘金額所需的最少硬幣數，這個值是之前計算過並保存在 **`method[]`** 陣列中的。
- **`+1`** 表示加上我們剛扣除的那一個 **`coin[i]`** 硬幣。

所以，**`method[j - coin[i]] + 1`** 這個表達式的含義是：如果我們從目標金額 **`j`** 中使用掉一個 **`coin[i]`** 硬幣，那麼加上這一個硬幣，總共需要的最少硬幣數是多少。