Posted on

[LeetCode] Coin Change 2

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有四種可能性]