貪婪演算法（Greedy Algorithm）

貪婪演算法就是每當執行區域性的抉擇時，都選擇當下有的選項中最好的一個選項

也就是說，貪婪演算法並不會考慮到未來，只考慮當下，因此對於某些情況下不一定能求出最佳解。但由於貪婪演算法的高效性以及其所求得的答案比較接近最佳解，也可以用作輔助演算法或者直接解決一些要求結果不特別精確的問題。

貪婪演算法是一個概念，他的精隨在於局部最佳解 (Local Optimal Solution)

把整個過程拆解成一個個步驟，然後針對第一個步驟找尋最佳解答，然後再找尋第二步驟的最佳解答，以此方式進行下去，最後的答案雖可能不是最佳解，但也會很接近最佳解。

包括 BFS、Dijkstra 都是貪婪演算法的一種。使用貪婪演算法雖然犧牲了一點點最終效益，卻能省下非常非常多的時間，因為他們十分簡單易寫。

常見的貪婪演算法

• Dijkstra's Algrithm： 單一路徑之最短距離
• Huffman's Algorithm： 霍夫曼編碼或壓縮算法
• 455. Assign Cookies
• 605. Can Place Flowers
• 122. Best Time to Buy and Sell Stock II
• 665. Non-decreasing Array

一、範例: 零錢問題

給定不同面額的硬幣 coins，和一個總金額 amount，求出最少硬幣的組合數。如果沒有任何一種硬幣組合能組成總金額，回傳 -1。

function coinChange(coins, amount) {
  let count = 0
  let total = 0
  for (let i = coins.length; i >= 0; i -= 1) {
    const coin = coins[i]
    while (total + coin <= amount) {
      count += 1
      total += coin
    }
  }
  return count
}

coinChange([1, 5, 10, 50], 90) // 5
coinChange([1, 5, 10, 50], 40) // 4
coinChange([1, 5, 10, 50], 15) // 2

對於新台幣硬幣面額，我們能使用貪婪演算法求出最佳解，但是，如果使用其他硬幣面額，就不一定能求出最佳解，必須要用到動態規劃 (dynamic programming) 法 。

動態規劃會記錄子問題解這點，是跟貪婪演算法的一大差異

貪婪演算法是每一步作出當前最佳解，持續把問題縮小，也就不會再回頭修改已經作的決定；動態規劃則是每一步都是基於前面已得出的子問題解來進行，並可能會更新已得到的答案。

用動態規劃 (dynamic programming) 解零錢問題

function coinChange(coins, amount) {
  let dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for (let coin of coins) {
    for (let i = coin; i <= amount; i += 1) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

coinChange([1, 3, 4], 6)

//coin=1,i=1,dp[1]=(dp[1],dp[0]+1)=(Infinity,1)=1 dp[1] [0,1,I,I,I,I,I]
//coin=1,i=2,dp[2]=(dp[2],dp[1]+1)=(Infinity,2)=2 dp[2] [0,1,2,I,I,I,I]
//coin=1,i=3,dp[3]=(dp[3],dp[2]+1)=(Infinity,3)=3 dp[3] [0,1,2,3,I,I,I]
//coin=1,i=4,dp[4]=(dp[4],dp[3]+1)=(Infinity,4)=4 dp[4] [0,1,2,3,4,I,I]
//coin=1,i=5,dp[5]=(dp[5],dp[4]+1)=(Infinity,5)=5 dp[5] [0,1,2,3,4,5,I]
//coin=1,i=6,dp[6]=(dp[6],dp[5]+1)=(Infinity,6)=6 dp[6] [0,1,2,3,4,5,6]
//coin=3,i=3,dp[3]=(dp[3],dp[0]+1)=(3,1)=1        dp[3] [0,1,2,1,4,5,6]
//coin=3,i=4,dp[4]=(dp[4],dp[1]+1)=(4,2)=2        dp[4] [0,1,2,1,2,5,6]
//coin=3,i=5,dp[5]=(dp[5],dp[2]+1)=(5,3)=3        dp[5] [0,1,2,1,2,3,6]
//coin=3,i=6,dp[6]=(dp[6],dp[3]+1)=(6,2)=2        dp[6] [0,1,2,1,2,3,2]
//coin=4,i=4,dp[4]=(dp[4],dp[0]+1)=(2,1)=1        dp[4] [0,1,2,1,1,3,2]
//coin=4,i=5,dp[5]=(dp[5],dp[1]+1)=(3,2)=2        dp[5] [0,1,2,1,1,2,2]
//coin=4,i=6,dp[6]=(dp[6],dp[2]+1)=(2,3)=3        dp[6] [0,1,2,1,1,2,2]
// return dp[6] === Infinity ? -1 : dp[6]
// return 2

先建立 amount + 1 陣列（+1 是為了對應總金額），將預設值設為 Infinity（便於與最小值的判斷），接下來遍歷每種面額對應的金額，並判斷是否為最小解。

動態規劃原理請見 動態規劃與分治法（Divide-and-Conquer） 一文

參考資料
1. 動態規劃與貪婪法題1：70 Climbing Stairs
2. （python版）第 2 章 最易懂的貪心演算法
3. 我的DSA日記 — 7
4. 30Day LeetCoding Callenge — Week4
5. JavaScript 學演算法（二十四）- 貪婪演算法
6. Greedy、Dynamic Programming 與 Divide and Conquer