# 322. Coin Change

### Leetcode

<https://leetcode.com/problems/coin-change/description/>

### 題目

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return `-1`.

You may assume that you have an infinite number of each kind of coin.

&#x20;

**Example 1:**

<pre><code><strong>Input: coins = [1,2,5], amount = 11
</strong><strong>Output: 3
</strong><strong>Explanation: 11 = 5 + 5 + 1
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: coins = [2], amount = 3
</strong><strong>Output: -1
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: coins = [1], amount = 0
</strong><strong>Output: 0
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

一開始的想法是將 `amount` 當做 DP 不斷累加的對象

範例：`coins = [1, 6, 7, 11], amount = 13`

一開始設初始值 `dp = [0]`，`dp[index]` 代表擲到 index 數字所需的最小次數，`dp[0]` 意思是擲到 0 所需的次數為零 (不需要擲)，接著從 1  遍歷到 amount: 13，計算每一輪中擲出 amount 的最低次數：

`amount: 1` 時，直接取第一個元素即可，最低次數為 1 => `dp = [0, 1]`

`amount: 2` 時，最低次數會是 `dp[1] + dp[1]`，代表擲出兩次 1

最低次數為 2  => `dp = [0, 1, 2]`

`amount: 3` 時，最低次數會是 `dp[2] + dp[1]`，代表擲出三次 1

最低次數為 3  => `dp = [0, 1, 2, 3]`

...

`amount: 6` 時，直接取第二個元素，代表擲出一次 6 => `dp[6] = 1`

`amount: 7` 時，直接取第三個元素，代表擲出一次 7 => `dp[7] = 1`

...

`amount: 13` 時，最低次數有可能會是：

先看 `coins` 中有沒有 13，有的話那就代表擲出一次 13 即可 => `dp[13] = 1`

接著最低次數的判斷可以根據之前計算出來的 DP 結果找出來：

* `dp[1] + dp[12]`  => 代表擲出 1 的最低次數 + 擲出 12 的最低次數
* `dp[2] + dp[11]` => 代表擲出 2 的最低次數 + 擲出 11 的最低次數
* ...
* `dp[6] + dp[7]` => 代表擲出 6 的最低次數 + 擲出 7 的最低次數

最後發現 `dp[6] + dp[7]` 是最低的擲出次數 2 => 所以 `dp[13] = 2`，代表擲出 13 的最低次數為 2

```javascript
var coinChange = function (coins, amount) {
    if (amount === 0) return 0;

    const dp = [0];

    for (let i = 1; i <= amount; i++) {
        const target = coins.find(coin => coin === i);
        if (target) {
            // 元素存在，擲一次就可以
            dp[i] = 1;
        } else {
            // 如果元素不存在，先把 dp[i] 設為最大值
            dp[i] = Number.MAX_SAFE_INTEGER;
            let match = false;
            // 遍歷前面 dp 的可能性
            for (let j = 1; j <= Math.floor(i / 2); j++) {
                if (dp[j] !== -1 && dp[i - j] !== -1) {
                    // 遍歷前面 dp 的可能性，找出最小擲出的次數
                    dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
                    match = true;
                }
            }
            
            // 怎麼擲都擲不出來的狀況設為 -1
            if (!match) {
                dp[i] = -1;
            }
        }
    }

    return dp[amount];
};
```

但這個方法會從 1 一路算到 amount，並且每一輪中還要遍歷原有的 dp 找出最小值，所以很明顯會 TLE

**時間複雜度：O(n^2)**

一開始 amount 要先遍歷一次(n)，接著乘以 **遍歷前面 dp 的可能性** 中的迴圈 (n)

* **方法二**

上面會 TLE 的主要原因在於遍歷 `amount` 的每一輪中都要遍歷前面 dp，時間複雜度會達到 `n^2`

```javascript
for (let j = 1; j <= Math.floor(i / 2); j++) {
    ...
}
```

如果 `coins = [71,440,63,321,461,310,467,456,361], amount = 9298`，因為 amount 的數字很大，採用方法一的方式很明顯會超時，所以我們必須換一個想法來找出 dp 的狀態轉移方程：

範例：`coins = [1, 6, 7, 11], amount = 13`

目標是求得 `dp[13]` 的話，可以先遍歷 `coins` 再求得各 dp 的值，例如：

* `coins[0] = 1`

  假設先擲出 1 的狀況，那麼 `dp[13] = 1 (擲出 1 的一次) + dp[12]`
* `coins[1] = 6`

  假設擲出 6 的狀況，那麼 `dp[13] = 1 (擲出 6 的一次) + dp[7]`
* `coins[2] = 7`

  假設擲出 7 的狀況，那麼 `dp[13] = 1 (擲出 7 的一次) + dp[6]`
* `coins[3] = 11`

  假設擲出 11 的狀況，那麼 `dp[13] = 1 (擲出 11 的一次) + dp[2]`

這樣其實我們就找出了 dp 的規律，`dp[13]` 最低的擲出次數就是以上四種狀況的最小值

而各 dp 的值也可以根據上面的這個規律求出來：

* `coins[0] = 1, amount = 1`

  擲出 1 的狀況，那麼 `dp[1] = 1 (擲出 1 的一次) + dp[1 - 1]`

  \=> `dp[1] = 1`，代表擲出一次 1
* `coins[0] = 1, amount = 2`

  擲出 1 的狀況，那麼 `dp[2] = 1 (擲出 1 的一次) + dp[2 - 1] = 1 + 1`

  \=> `dp[2] = 2`，代表擲出兩次 1

  ...

  ...
* `coins[1] = 6, amount = 7`

  擲出 6 的狀況，那麼 `dp[7] = 1 (擲出 6 的一次) + dp[7 - 6] = 1 + 1`

  \=> `dp[7] = 2`，代表擲出一次 6 + 一次 1
* `coins[1] = 6, amount = 8`

  擲出 6 的狀況，那麼 `dp[8] = 1 (擲出 6 的一次) + dp[8 - 6] = 1 + 2`

  \=> `dp[8] = 3`，代表擲出一次 6 + 兩次 1

依照上面的規律寫出如下的程式碼：

```javascript
var coinChange = function (coins, amount) {
    if (amount === 0) return 0;

    const dp = [0];

    // 先遍歷 amount
    for (let i = 1; i <= amount; i++) {
        // 因為 dp 判斷會取最小值，初始值要設為最大值
        dp[i] = Number.MAX_SAFE_INTEGER;

        // 再遍歷 coins
        for (let j = 0; j < coins.length; j++) {
            const coin = coins[j];
            // 如果 coin 小於當前的 amount，代表可以擲出來 (ex. coin = 2, i = 3)
            if (coin <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }

    // 如果 dp[amount] 一樣是最大值，代表擲不出來
    return dp[amount] === Number.MAX_SAFE_INTEGER ? -1: dp[amount];
};
```

**時間複雜度：O(m x n)**  - amount \* coins

### 參考資料

{% embed url="<https://ithelp.ithome.com.tw/articles/10221988>" %}
