# 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++):

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];

---

## 參考資料
台中女中程式解題系統

/**********************************************************************************/
/*  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;
}