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