Coin Change 是動態規劃的經典題目，題意簡述為：
給定一組不同面額的的硬幣和金額，問：若要湊成該金額最少可以使用幾枚硬幣？這裡先假設每種面額的硬幣都有無限多個。
例如給的硬幣面額有 [1, 2, 5]，要湊成 11元，最少硬幣的湊法為：使用 2 個 5 元硬幣加 1 個 1 元硬幣，所以回傳 3。
做這個題目時，首先想到的直覺解法是用貪心法（後來才知道原來自己用的方法是貪心法），不過結果發現貪心法在某些情況上會無法得出最優解：
概念大概是從最大的面額開始拿，拿到不能再拿時才改拿第二大面額，但如果碰到像上述的 test case 的情況時，會變成找不出最佳解。
於是爬文得知這題需要用動態規劃解，一直以來對這個方法一知半解的我，翻了很多教學資源，大約知道動態規劃需要先找出 base case 和轉移方程式，但沒學過離散數學，只能勉強聽懂遞迴式推演的部分，而實際要怎麼找出那個規律根本無法只靠算式就得出答案，後來好不容易翻到這個教學，覺得對我這種基礎不佳的人非常友善，沒錯，就是圖解～以下把該教學的推演過程消化過後用文字說明一遍。
首先以面額 [1, 2, 5] 湊出 11 的最少硬幣數為多少為例：
當要湊出11時，會面臨三種狀況的選擇：
- 若選了1，要面臨湊出價值為10的情況
- 若選了2，要面臨湊出價值為7的情況
- 若選了5，要面臨湊出價值為6的情況
而我們可以先定義一個函式：湊出價值為 n 時需要的最少硬幣數為 f(n)
首先在 f(0) 的情況，也就是要湊出 0 時，需要的最少硬幣數為 0 （因為不需要任何硬幣即可湊出 0）。
在 f(1) 的情況，也就是要湊出 1 時，若取 1 個面額 1 的硬幣，需要面臨湊出價值 0 (1–1=0)的情況，所以取面額 1 時需要的硬幣數為 1+ f(0) = 1 （因為 f(0)剛剛已經算過了，查表即可得值）。而這時面額 2, 5 都大於 1 不能取。所以這三種情況裡面取最小值的硬幣數就是 1，得出 f(1) = 1 填入。
在 f(2) 的情況，若取 1 個面額 1 的硬幣，需要面臨湊出價值 1 的情況，所以取面額 1 時需要的硬幣數為 1+ f(1) = 2；若取 1 個面額 2 的硬幣，需要面臨湊出價值 0 的情況，所以取面額 2 時需要的硬幣數為 1+ f(0) = 1，而面額 5 大於 2 不能取。
以此類推把表格填完，可以歸納出一個式子：
// n 為金額， c1… ck為面額f(n) = Min( 1 + f(n- c1), 1+ f(n-c2),…, 1+f(n-ck) )
有了這個式子，程式就很容易可以寫出來了：
var coinChange = function(coins, amount) {
const dp = [0]
for (let i = 1; i <= amount; i++) {
let min = Infinity;
for(let j = 0; j < coins.length; j++) {
// 若金額（amount）小於面額，或是剩下的值無法湊出來，就跳過不算 if (i - coins[j] < 0 || dp[ i - coins[j] ] === -1) continue
min = Math.min(min, 1 + dp[ i - coins[j] ])
} dp[i] = min === Infinity ? -1 : min
} return dp[amount]
};
總之到這邊為止對動態規劃的理解大概是，必須要先找出某種規律，利用前一個問題算出的答案去解下一個問題，所以 base case 很重要，若 base case 沒有先定義好，後面也就很難算出來。
自己對於演算法還有很多需要學習的部分～若有任何理解不正確的地方也歡迎提出指教！
