<Day10- 補充知識>

1. 遞迴 必須有base case = 停止點 ,防止無限遞迴
   1. 防止無限, 瀏覽器都有自己的上限有了 stack overflow error 根據瀏覽器有所不同
      1. ES6 tail call optimization 如果函數內最後一個操作是呼叫別的函數, 會藉由jump 而非subroutine call來控制 -> 所以他可以一直執行下去
   2. 應用 斐波那契數列
   3. why 遞迴 ？較易理解 程式碼較少 較易解決問題
2. 動態規劃 Dynamic Programming DP 不等於分治法
   1. 將複雜問題分解成更小的子問題來解決的最佳化技術
   2. 流程
      1. 定義子問題
      2. 實作要反覆執行而解決子問題的部分
      3. 識別並解出基本情況
   3. 實例
      1. 揹包問題
      2. 最常公共子序列
      3. 矩陣鏈相乘
      4. 硬幣找零
3. 貪婪演算法
   1. 遵循一種近似解決問題的技術，期盼透過每個階段的局部最佳選擇，進而達到全域最佳解答
4. 大O表示法
   1. 如何衡量演算法的效率? 大O -> CPU時間佔用

補充：
分治 把問題分解成相互獨立的子問題，組合他們的答案
動態規劃 將問題分解成相互依賴的子問題

//other
function fibonacci(numb){
  if(num === 1 || num ===2){
    return 1
  }
  return fibonacci(num-1)+ fibonacci(num -2)
}

function fib(num){
  let n1 = 1, n2 = 1, n= 1
  for (let i =3 ; i <= num; i++){
    n = n1+n2
    n1 = n2
    n2 = n
  }
  return n
}

//最小找錢幣法 DP
function MinCoinChange(coins){
  let coins = coins
  let cache = {}

  this.makeChange = function(amount){
    let me = this
    if (!amount){
      return []
    }
    if (cache[amount]){
      return cache[amount]
    }
    let min = [], newMin, newAmount

    for(let i = 0 ; i < coins.length; i++){
      let coin = coins[i]
      newAmount = amount - coin
      if (newAmount >= 0){
        newMin = me.makeChange(newAmount)
      }
      if (
        newAmount >= 0 && (newMin.length < min.length -1 || !min.length) && (newMin.length || !newAmount){
          min = [coin].concat(newMin)
          console.log(`new Min ${min} for ${amount}`)
        }
      )
      return (cache[amount] = min)
    }
  }
}
//貪婪演算法
function MinCoinChange(coins){
  let coins = coins
  this.makeChange =  function(amount){
    let change = [], total = 0
    for(let i = coins.length ; i >= 0 ; i--){
      let coin = coins[i]
      while (total + coin <= amount){
        change.push(coin)
        total += coin
      }
    }
    return change
  }
}

感想

這30天(我應該快60天)來起起伏伏，從一開始想要挑戰一次兩個到最後只能免強完成一個，
與期末考時間相撞真的自找麻煩，但整體而言是不錯的，有找到一開始想要進步的方向，真的就是要"開始"寫東西。
其他戰友們的成果都很優秀，寒假會好好把之前follow的文章看完，學學資安，學學物聯網等等，感覺都好好玩。

一直到今天才好像聽懂為什麼大家都說javascript比你想像的大很多強很多，看了一些演講也才慢慢懂為什麼會是這樣的語法等等，也因此想在最後10天回歸到基本，去看看如何用javascript來學習基本基本的資料結構和演算法等等

明年會再好好努力，謝謝大家。