---
# System prepended metadata

title: Dynamic Programming | 動態規劃

---

# Dynamic Programming | 動態規劃
By Aaron Lee | Apr 1

## 題目
- 假如你是一個超商店員，需要找錢給別人，並且要找最少的數量的硬幣
- 這個國家的貨幣有 [A] 種
- 如何找到使用最少貨幣的方法（只需要知道用了多少硬幣就好）


## 你知道的東西
- N : 需要找多少錢 (1 <= N <= 100)
- COIN_TYPE[] : 有什麼硬幣


## 範例題目

- 貨幣種類:

| 1   | 4   | 8   | 10  | 13  | 20  | 23  |
| --- | --- | --- | --- | --- | --- | --- |
- 要找 18 元
- 你會怎麼解這題？

---

## 一般人會怎麼想
- 從最後面找，最大的可以用的就使用
    1. `23 >= 18` → 不使用
    1. `20 >= 18` → 不使用
    1. `13 <= 18` → 使用 並且改成找 `18 - 13 = 5`, 使用 `1` 個硬幣
    1. `13 >= 5`  → 不使用
    1. `10 >= 5`  → 不使用
    1. `8  >= 5`  → 不使用
    1. `4  <= 5`  → 使用 並且改成找 `5 - 4 = 1`, 使用 `2` 個硬幣
    1. `4  >= 1` → 不使用
    1. `1  >= 1` → 使用 並且已經找完 `1 - 1 = 0`, 使用 `3` 個硬幣
- 一樣的東西表格化版本

| Step | N (目前找的數) | COIN (硬幣, 從大找到小) | 判斷結果 | AMT (所需的硬幣數量) |
| ---- | ------------ | --------------------- | ------ | ----------------- |
|  初始 | 18 | 23 | -- | 0 |
|  1 | 18 | 23 | 不使用 | 0 |
|  2 | 18 | 20 | 不使用 | 0 |
|  3 | 18 | 13 | 使用，更新 `N = N - COIN = 5` | `AMT = AMT + 1 =` 1 |
|  4 | 5 | 13| 不使用 | 1 |
|  5 | 5 | 10| 不使用 | 1 |
|  6 | 5 | 4 | 使用，更新 `N = N - COIN = 1` | `AMT = AMT + 1 =` 2 |
|  7 | 5 | 4 | 使用，更新 `N = N - COIN = 1` | `AMT = AMT + 1 =` 2 |
|  8 | 5 | 4 | 不使用 | 2 |
|  9 | 5 | 1 | 使用，更新 `N = N - COIN = 0` → 結束 | `AMT = AMT + 1 =` 3 → 結束 |

### BUT, 這個想法是錯誤的 (而且這題的正解是 `2`，因為 `8 + 10 = 18` → 最少的硬幣組)

---
## 正確做法 (Dynamic Programming | 動態規劃)
- 新增一個 陣列 DP ，並且動態更新他（一直更新他）
- 黑人問號我知道 嘿嘿
- 解釋（表格就好了不然我打到死掉 QQ)


| 貨幣（從小到大）:arrow_down:       |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  | 10  | 11  | 12  | 13  | 14  | 15  | 16  | 17  | 18  |
|:--------------------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|             **1**              |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  | 10  | 11  | 12  | 13  | 14  | 15  | 16  | 17  | 18  |
|             **4**              |  0  |  1  |  2  |  3  |  1  |  2  |  3  |  4  |  2  |  3  |  4  |  5  |  3  |  4  |  5  |  6  |  4  |  5  |  6  |
|             **8**              |  0  |  1  |  2  |  3  |  1  |  2  |  3  |  4  |  1  |  2  |  3  |  4  |  2  |  3  |  4  |  5  |  2  |  3  |  4  |
|            **10**              |  0  |  1  |  2  |  3  |  1  |  2  |  3  |  4  |  1  |  2  |  1  |  2  |  2  |  3  |  2  |  3  |  2  |  3  |  2  |
|            **13**              |  0  |  1  |  2  |  3  |  1  |  2  |  3  |  4  |  1  |  2  |  3  |  4  |  2  |  1  |  2  |  3  |  2  |  2  |  3  |
 - 結束（bc 20 >= 18) :+1: 
 - 好你一定不知道我在寫什麼 :smirk:

### 解釋
 - 第一個 column (:arrow_down:) 是代表正在比較的硬幣值
 - 第一個 row (:arrow_right:) 是代表要找的錢（如果把全部都列出來會大幅減少運算的時間）→ 這個稱為檢索的值
 - 中間每一個都是各值最少的貨幣值（可以使用上面的貨幣，但不能使用下面的）
 - 數學證明這個做法會有最佳的答案
```
重複 需要找多少錢 遍
    如果 (DP 的第 [檢索的值 - 正在比較的硬幣值] 的值 + 1 < DP 的第 [檢索的值] 的值) 就
        DP 的第 [檢索的值] 的值 *改成* DP 的第 [檢索的值 - 正在比較的硬幣值] 的值 + 1
最少硬幣和為 DP 的第 [需要找多少錢] 的值
```
 - Code form (C/C++):
```cpp=
for (int i = 0; i <= N; i++) // This just means repeat N times
    if ((DP[i - COIN_TYPE] + 1) < DP[i])
        DP[i] = DP[i - COIN_TYPE] + 1;
int ANS = DP[N];
```

---

## 參考資料
台中女中程式解題系統
```cpp=
/**********************************************************************************/
/*  Problem: b028 "忙碌的超商店員" from 動態規劃-最少零錢數                                       */
/*  Language: C++                                                                 */
/*  Result: AC (3ms, 124KB) on ZeroJudge                                          */
/*  Author: aaronlee at 2021-03-22 22:26:10                                       */
/**********************************************************************************/

#include <stdio.h>
const int COIN_TYPE[6] = {1, 5, 10, 12, 16, 20};

int main() {
  int N;
  scanf("%d", &N);
  int arr[N];
  for (int i = 0; i <= N; i++)
    arr[i] = i;

  for (int i = 0; i < 6 && COIN_TYPE[i] < N; i++)
    for (int j = COIN_TYPE[i]; j <= N; j++)
      if ((arr[j - COIN_TYPE[i]] + 1) < arr[j])
        arr[j] = arr[j - COIN_TYPE[i]] + 1;
  printf("%d", arr[N]);
  return 0;
}

```