簡單敘述一下題目目標：
這一題我們要從Input Array（給你的一袋金幣）中，想辦法以金幣總數量最少的目標湊出他要的總額。如果辦不到請回傳-1。

在開始動手之前，想先簡單介紹一下，動態規劃 Dynamic Programming (DP)的觀念。
動態規劃是一種解決遞迴型態問題的策略，他由子問題開始解決，而最終的結果會參考到解決子問題過程中所獲得的解。

如果以昨天 Day02: Fibonacci的問題來看，我們在第二個方法中其實就是把過程所算出來解存到一個hashTable,最後以查表的方式來減少重複的計算量，這種以空間換取時間的方式，是動態規劃的主要精神。

那什麼時候要用DP來解問題呢？
如果這個問題，具有Optimal substructure的性質，我們就可以用DP的策略。

Optimal substructure: 當問題的最佳解(optimal solution)是由子問題之最佳解所構成，我們就會稱這個問題有Optimal substructure性質

如果有Optimal substructure的問題採用遞迴方式解決，就容易有不斷重複解相同問題的情況(Overlapping subproblem)。所以我們可以計算一次子問題並存在表格中，最後建構出原問題的解，這種Bottom-up的方式就是DP的策略。

介紹到這裡，廢話不多說，我們來解這題問題吧！

以題目給的範例(我先把amount改成7，為了畫圖不要畫太長 (-//-)a)

Input: coins = [1,2,5], amount = 7
Output: 2
Explanation: 7 = 5 + 2

我們每次都拿當下的值去扣掉你目前手上硬幣的錢，拿餘數去查之前做完的最佳解，
所以是１＋（餘數的最佳解）

我們把１＋（餘數的最佳解）和目前的最佳解做比較，如果比較好就取代掉
換成程式碼就是

if denom <= amount:
  min(nums[amount], 1 + nums[amount - denom])

從上圖，相信可以很容易理解時間複雜度會是Ｏ(nd)-> 長乘以寬的感覺~
其中n是我們想要得到的值（amount)，而d就是input array我們擁有不同金幣的個數
空間複雜度 Space:O(n) 需要n的空間來暫存當下的結果

最後來寫code吧！

var coinChange = function (coins, amount) {
// 先建立一個紀錄結果的空間 都先塞無限大
  const numberOfCoins = new Array(amount + 1).fill(Infinity);
  numberOfCoins[0] = 0;
// 把input給的金幣拿出來檢查
  for (const denom of coins) {
    for (let total = 0; total < numberOfCoins.length; total++) {
      if (denom <= total) {
        numberOfCoins[total] = Math.min(numberOfCoins[total], numberOfCoins[total - denom] + 1)
      }
    }
  }
  return numberOfCoins[amount] !== Infinity ? numberOfCoins[amount] : -1;
};

明天題目預告：
再來一題錢幣問題－ Smallest Non-constructible Value