月份: 2022 年 10 月

Maximum Value of K Coins From Piles

這是遞迴方式的寫法, 但我可能存太多垃圾資訊,當k值變大之後,會發生heap allocation錯誤的問題,也受限於遞迴的限制當k變大效率非常差…..
看來又要動態規劃(哭), 晚點再來補上改善版

/**
* @param {number[][]} piles
* @param {number} k
* @return {number}
*/
var maxValueOfCoins = function (piles, k) {
let rootNode = new node(piles.length, k);
let maxResult = addAllChildrenForThisNode(rootNode, piles, 0);
console.log(rootNode.toObject())
return maxResult
};
function addAllChildrenForThisNode(node, piles, maxResult) {
for (let i = 0; i < node.pilesPointer.length; i++) {
if (node.pilesPointer[i] + 1 < piles[i].length) {
let y = node.pilesPointer[i] + 1;
let newNode = node.addChild(piles[i][y], i, y);
console.log(newNode.deep)
if(newNode.deep < newNode.maxSelectNum){
maxResult = addAllChildrenForThisNode(newNode, piles, maxResult)
}else{
maxResult = Math.max(newNode.currentValue, maxResult)
}
}
}
return maxResult
}
function node(pilesNum, maxSelectNum) {
this.currentValue = 0;
//樹的鏈結資料
this.deep = 0;
this.parent = undefined;
this.children = [];
//x代表在哪個piles, y代表在該piles的深度
this.indexX = undefined;
this.indexY = undefined;
//用來儲存這個node位置所有的piles的y座標
this.pilesPointer = new Array(pilesNum).fill(-1);
this.maxSelectNum = maxSelectNum;
this.addChild = function (num, indexX, indexY) {
let child = new node(this.pilesPointer.length, this.maxSelectNum);
child.deep = this.deep + 1;
child.parent = this;
child.currentValue = this.currentValue + num;
child.indexX = indexX;
child.indexY = indexY;
child.pilesPointer = this.pilesPointer.slice(0);
child.pilesPointer[child.indexX] = indexY;
this.children.push(child);
return child
}
this.toObject = function () {
let children = [];
for (let child of this.children) {
children.push(child.toObject())
}
return {deep:this.deep, value: this.currentValue , children: children}
}
}

console.log(maxValueOfCoins([[80,62,78,78,40,59,98,35],[79,19,100,15],[79,2,27,73,12,13,11,37,27,55,54,55,87,10,97,26,78,20,75,23,46,94,56,32,14,70,70,37,60,46,1,53]],5))

Coin Change2

這也是一題動態規劃的題目，但是比起上一題，上一題每一個暫時儲存的東西是有意義的，我們可以了解說每一個的暫時狀態是某個數字用所給的硬幣列表裡，能用最少數量達成答案的數目，但是這一題的中間狀態所儲存的真的就是『中間的狀態』，我是看著別人的答案去回推理論的，真的很難想像在遇到這樣的問題時，該用什麼角度去把複雜的問題拆分，並找尋出重複步驟並找到可暫存狀態來計算出最終結果。

這是最後的結果

var change = function(amount, coins) {
let dp = new Array(amount+1).fill(0);
dp[0]=1;
for(let coin of coins){
for(let i=coin;i<=amount;i++){ dp[i]+=dp[i-coin]; } } return dp[amount] }; [/code] 大概解釋一下解題的思緒，首先就是最重要的，先設定一個暫存動態編程的序列

dp

，這裡面的值只是儲存一個暫時的狀態，讓我們在計算下一個值時可以拿前一個運算到一半的值來繼續運算，長度為amount+1（這樣才存的到

dp[amount]

）。

接下來很重要的是把

dp[0]=1

, 這是所有計算的起點, 代表說在一個分解狀態下，若自己可以被自己整除，那就可以有一種解法

若題目是coins=[2,5,8], amount=16時：

我們可以先觀察在

coins:[2], amount:16

時，
這樣的半狀態會得到：

dp = [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]

這個的意思是，若是coins只有2時，可以用2組成0, 2, 4, 6, 8, 10, 12, 14, 16，皆只有一種組法。

接下來我們再把5加進去，但是因為以coins=[2,5]來說，我們可以把任務拆細，若是要組成16，我們要避免掉重覆的狀態，也就是說
我們可以思考，因為5,5,2,2,2和2,2,5,5,2其實是相同的答案，以2,2,2,5,5來說，其實是單純用2coin*3個＝6和單純用5coin*2個＝10,
那麼就可以開始計算，用5和2共同組成的狀況下，五的分佈是如何呢？

amount為16，則5有可能有分成：1個5(這時會需要單純用2組成11)和2個5(這時會需要用2組成6)和3個5(這時會需要用2組成1)三種可能性，這時參照上面coins=[2]的dp，會知道用2組成11的狀況和用2組成1狀況是0個，代表只會增加2個5的狀況。

但是動態編程當然沒這麼容易思考（真哭），因為這邊的dp存的是一個暫時半狀態的對照表，會需要算出從5~16所有可用[2,5]組成的，需要較完整的對照表。

首先很重要的，為什麼要從五開始，因為一定要大於五才有可能可以用五組成結果，並且如同dp[0]一樣，dp[5]因為coins有5，一定會多一種5的組合法。
從上面的推論我們可以觀查到要知道有沒有機會使用5這個coins來組成結果，主要要觀察『要組成總數』減掉現有coin的面額的數字，能不能用2組成。

所以若要知道6能不能用[5,2]組成，就要查coins:[2]所暫存的表的

dp[6(要組數字）-5(現有硬幣)]＝dp[1]（能不能用2組成1） = 0

，可得知是0種可能，以此類推。
這邊非常重要的是一定要從小到大，因為才可以讓狀態累加，我們先得知5可以組成5，把dp[5]＝1(本來只有coins:2時是0)，而在算10時，才能得到dp[10-5]=1(得知可以使用5來組成10)，外加單純用2組成10的可能性（當coins=[2]時dp[10]為1），可知10這個數字可單純用5組成也可用[2,5]組成，所以共有2種可能性，然後把dp[10]更新為2

接著在算dp[15]時才能夠利用dp[15-5]=dp[10]=2，再加上當coins=[2]時的dp[15]＝0，得知dp[15]為2

以下為coins=[2,5]時的dp對照表

dp= [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2]

接下來就是再相同的步驟再把coin 8加進coins列表裡。以同樣的步驟和概念，就可以得到

dp=[1, 0, 1, 0, 1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 3, 3, 4]

最後推得用[2,5,8要組成16有四種可能性]

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

結果至少擊敗了72.28%的人,累了…先這樣吧XDD