觀前提醒：

1. 我預設大家已經先思考並分析過題目，沒啥想法才開始 google 找解題靈感。若無，建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法。
2. 承上，既然已經有思考過了，那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了，那我可能解題想法 & 心得的部分就不會寫太多，免得干擾你的思考。
3. 所有解法都是已經取得系統的 Accepted，但或許不是最優解法，請多包涵。
4. 若對於解法不太懂，可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
5. 最後，歡迎在下面留言指教~教學相長才會進步歐~

題目

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:

• 0 ≤ N ≤ 30.

解題想法

1. 關於數學概念，可參考此連結 -- Fibonacci number
2. 更廣義的數學概念，可參考此連結 -- Recursion
3. 實際操作的部分，建議直接採取 Dynamic Programming (Divide and Conquer + Memoization)，並從 Bottom-up 的方式來寫CODE會最好理解。(詳情可參考我的前篇文章)

CODE

/**
 * @param {number} N
 * @return {number}
 */
var fib = function (N) {
  const table = [0, 1];
  if (N < 2) {
    return table[N];
  }
  for (let i = 2; i <= N; i++) {
    table.push(table[i - 1] + table[i - 2]);
  }
  return table[table.length - 1];
};

心得

只要能掌握住費波納契數列的基本概念，再配上 DP 的解題方式，其實問題沒有大家想像中的恐怖~
希望大家看到 Time Limit Exceeded 再也不會心慌慌~
Dynamic Programming 是居家旅行必備良伴(?

謝謝大家的收看，LeetCode 小學堂我們下次見~