[LeetCode] Coin Change – Claire's Blog

https://leetcode.com/problems/coin-change

最近開始刷leetcode覺得思考這些邏輯問題還滿好玩的
第一個刷的是這個,他是一個動態規劃的題目

一般我們在思考的時候會去思考以錢幣為基準,例如1,3,5的錢幣要怎麼湊成11元,我們會拿1,3,5去隨機湊硬幣,但是當數值大了以後,要計算最小的錢幣組合就會變成很困難.

像這種極限求值就會需要將思考轉換過來, 我們可以一步步的拆解, 先了解1,3,5,若要組成1是用幾個(1個1),那組成2要用幾個(2個1),若要組成3要用幾個,到3時我們就會發現,3可以用”3個1″或”1個3″組成, 這時候就可以來比較誰用的硬幣比較少,然後把最小可組成的數字”1″存到可組成結果為3的陣列。
接下來在思考4的時候,我們就可以思考4減掉硬幣1,也就是3,的最小使用硬幣數量,那就代表我們使用3,再加上硬幣1,可以組成4。接下來算要組成6要幾個硬幣,6減掉硬幣3,可以拿到硬幣3要用幾個硬幣,所以就是硬幣3使用的硬幣數量+1。

var coinChange = function (coins, amount) {
    if (amount == 0) return 0;
    let amountRecord = []
    amountRecord[0] = 0
    lastExistResult = 0
    minCoin = Math.min(...coins);
    //紀錄這些硬幣能夠組合成的數值所使用的硬幣數, 並用這些數值來推算目標所需的硬幣
    for (var currentAmount = 1; currentAmount <= amount; currentAmount++) {
        amountRecord[currentAmount] = Infinity
        if (currentAmount + minCoin >= lastExistResult) {
            for (var coin of coins) {
                if (coin <= currentAmount) {
                    //尋找這一個數字可不可以用之前可組成的硬幣加上其中一個新的硬幣來滿足(以確認是最小的硬幣數目)
                    amountRecord[currentAmount] = Math.min(amountRecord[currentAmount], amountRecord[currentAmount - coin] + 1);
                }
            }
        }
        if (amountRecord[currentAmount] != Infinity) {
            lastExistResult = amountRecord[currentAmount];
        }
    }
    console.log(amountRecord)
    return amountRecord[amount] == Infinity ? -1 : amountRecord[amount]
};

var coinChange = function (coins, amount) {

if (amount == 0) return 0;

let amountRecord = []

amountRecord[0] = 0

lastExistResult = 0

minCoin = Math.min(...coins);

//紀錄這些硬幣能夠組合成的數值所使用的硬幣數, 並用這些數值來推算目標所需的硬幣

for (var currentAmount = 1; currentAmount <= amount; currentAmount++) {

amountRecord[currentAmount] = Infinity

if (currentAmount + minCoin >= lastExistResult) {

for (var coin of coins) {

if (coin <= currentAmount) {

//尋找這一個數字可不可以用之前可組成的硬幣加上其中一個新的硬幣來滿足(以確認是最小的硬幣數目)

amountRecord[currentAmount] = Math.min(amountRecord[currentAmount], amountRecord[currentAmount - coin] + 1);

}

if (amountRecord[currentAmount] != Infinity) {

lastExistResult = amountRecord[currentAmount];

}

console.log(amountRecord)

return amountRecord[amount] == Infinity ? -1 : amountRecord[amount]

};

這個JS的效能只贏了32.59%的人

覺得不太開心(?)
所以我把console.log拿掉,再把let amountRecord = []; amountRecord[0] = 0;改成一行let amountRecord = [0](是有沒有這麼無聊)

接著我突發奇想,想說若是這個數字可用硬幣湊齊, 下個數字如果小於最小的coins數字的話,可以省略(如硬幣是10,15,18, 但是要組成11,很明顯就不可能會有結果,因為11-10小於10)

PS: 但是測試後其實拿掉console.log影響最大XD

var coinChange = function (coins, amount) {
    if (amount == 0) return 0;
    let amountRecord = [0]
    lastExistResult = 0
    minCoin = Math.min(...coins);
    //紀錄這些硬幣能夠組合成的數值所使用的硬幣數, 並用這些數值來推算目標所需的硬幣
    for (var currentAmount = 1; currentAmount <= amount; currentAmount++) {
        amountRecord[currentAmount] = Infinity
        if (currentAmount + minCoin >= lastExistResult) {
            for (var coin of coins) {
                if (coin <= currentAmount) {
                    //尋找這一個數字可不可以用之前可組成的硬幣加上其中一個新的硬幣來滿足(以確認是最小的硬幣數目)
                    amountRecord[currentAmount] = Math.min(amountRecord[currentAmount], amountRecord[currentAmount - coin] + 1);
                }
            }
            if (amountRecord[currentAmount] != Infinity) {
                lastExistResult = amountRecord[currentAmount];
            }
        }
    }
    return amountRecord[amount] == Infinity ? -1 : amountRecord[amount]
};