iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 27
2
Software Development

前端工程師用 javaScript 學演算法系列 第 27

[LeetCode #322] Dynamic Programming

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) {
    
};

轉成圖片大家可能比較好懂到底要幹嘛 XD,其實題目就是說:
有不同面額的硬幣(數量無限),我就以有 1, 2, 5 面額的硬幣為例,如何使用最少硬幣數湊成 11 ? 回傳硬幣數
https://ithelp.ithome.com.tw/upload/images/20190928/20106426w0YJHSPsXV.jpg
一開始腦中可能像我一樣一片空白,不過先不要這麼貪心急著找答案,就先用最簡單想法來試試吧。

Think

極限值/特殊狀況

有可能有負的面額

大概會怎麼解

試想假如每種面額的硬幣都會用到
$1 + 10 = 11
$2 + 9 = 11
$5 + 6 = 11
https://ithelp.ithome.com.tw/upload/images/20190928/20106426PtJsCYCKKg.jpg
接下來 10、9、6 又可以寫成兌換硬幣的組合,例如 10 = 5 + 5, 9 = 5 + 2 + 2, 6 = 5 + 1

總結以上,由於我們要找出最少數目,所以可以這樣想

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

其中 1 分別代表兌換面額 $1、$2、$5 的數量,而 f(n) 表示兌換 n 元所需最少數量。程式可以簡化成

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

然後繼續跟一直重覆步驟直到找到 f(0),f(0) 代表當下硬幣數量就可以代表需要的錢,
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) 了
...

看到 f(0) 代表找到啦
amount 5 只有一種方式就是直接拿 1 個 $5,往回推算

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

所以答案 2 個 $5,1 個 $1,總共 3 個硬幣,答案就是 3
https://ithelp.ithome.com.tw/upload/images/20190928/20106426y7hN2osQyx.jpg

哪種資料結構解

思考了之後才會知道會往動態規劃方向走

完整程式碼

今天工作實在太忙,連在飛機上都還努力拼寫鐵人賽!

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

參考資料

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

歡迎追蹤我的部落格,除了技術文也會分享一些在矽谷工作的甘苦。


上一篇
動態規劃 Dynamic programming
下一篇
[LeetCode #167] Two Pointer
系列文
前端工程師用 javaScript 學演算法32
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

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

這篇真的好難啊!

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

基本上到現在我遇到 DP 題還是都會想超級久,然後要看別人解答 T___T,不像 two pointer, stack 看到都知道大概怎麼解了

繼續研究後,發現這個做法好像屬於貪心算法。

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

(http://www.conardli.top/docs/algorithm/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95.html)

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

謝謝你提供的資料連結 /images/emoticon/emoticon34.gif

1
Dylan
iT邦新手 3 級 ‧ 2021-02-22 15:28:43

還是有點不太明白 1 + out[index - coins[i]] 這段
/images/emoticon/emoticon06.gif

Chris iT邦新手 5 級 ‧ 2022-04-15 12:18:27 檢舉

out[index - coins[i] 是去 out 這個 table 裡面拿到上次紀錄的這個總數(index - coins[i]) 是用幾個硬幣計算的

然後在 +1 (這次的硬幣) 就會是 index 這個總數總共需要多少的硬幣數量

希望這樣有幫到你

我要留言

立即登入留言