DAY 27
2
Software Development

# 322. Coin Change

``````// Question:
You are given coins of different denominations and a total amount of money amount.
Write a function to compute 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.

Note:
You may assume that you have an infinite number of each kind of coin.
``````
``````// Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

``````
`````` * @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {

};
``````

### Think

#### 大概會怎麼解

\$1 + 10 = 11
\$2 + 9 = 11
\$5 + 6 = 11

``````f(11) = Math.min(1 + f(10), 1 + f(9), 1 + f(6))
``````

``````f(11) = Math.min(f(10), f(9), f(6))
``````

ex. f(5) = 1 + f(0), 1 代表 \$5，只要 1 個 \$5 就可以達到 amount 5

#### 分解步驟

``````// 第一次
f(11) ＝ Math.min(1 + f(10), 1 + f(9), 1 + f(6))

// 第二次
f(10) = Math.min(1 + f(9), 1 + f(8), 1 + f(5))
f(9) = Math.min(1 + f(8), 1 + f(7), 1 + f(4))
f(6) = Math.min(1 + f(5), 1 + f(4), 1 + f(1))

// 第三次
f(9)) = Math.min(1 + f(8), 1 + f(7), 1 + f(4))
f(8) = Math.min(1 + f(7), 1 + f(6), 1 + f(3))
f(5) = Math.min(1 + f(4), 1 + f(3), 1 + f(0))  // 看到 f(0) 了
...
``````

amount 5 只有一種方式就是直接拿 1 個 \$5，往回推算

``````f(5) = 1
f(10) = 1+ 1 = 2
f(11) = 1 + 2
``````

#### 完整程式碼

``````var coinChange = function(coins, amount) {
if (!amount || !coins.length) {
return 0;
}

let out = [0];
let i, l;
let index = 1;

while (!out[amount]) {
out[index] = Infinity;
for (i = 0, l = coins.length; i < l; i++) {

if (coins[i] <= index) {
out[index] = Math.min(out[index], 1 + out[index - coins[i]]);
}

}
index++;
}

return out[amount] === Infinity ? -1 : out[amount];
};
``````

### 參考資料

``````如有錯誤或需要改進的地方，拜託跟我說。

``````

### 1 則留言

0
kaikaitaiwan
iT邦新手 5 級 ‧ 2019-10-20 22:29:38

hannahpun iT邦新手 5 級 ‧ 2019-10-21 02:42:54 檢舉

"貪心算法與動態規劃的不同在於它對每個子問題的解決方案都作出選擇，不能回退，動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能，而回溯算法就是大量的重複計算來獲得最優解。"

hannahpun iT邦新手 5 級 ‧ 2019-11-09 04:45:30 檢舉