觀前提醒：

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

題目

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

• 1 <= n <= 45

解題想法

當各位把紙筆準備好，把第一階到第 4 or 5 階答案寫下來後，你會發現這是一題相當經典的遞迴問題：當子問題與原問題完全相同，只有範圍不同，此現象為 Recurrence ，這表示再度出現、一再出現之意。

這題如果用暴力解的話，我猜時間應該會超過，所以建議還是採取 Dynamic Programming (Divide and Conquer + Memoization)的方式來解決比較好。且思維方式，建議再加入 Bottom-up 的方式來解題更好。

其中心思想為：每階的抵達方式，皆為前兩階抵達方式之和。

*p.s 這跟遞迴函數的"Recursion"不同，Recursion 比較嚴謹，是指數學上的遞迴。(參考連結)而 Recurrence 比較偏向是廣義的、各種形式上反覆出現的情況(參考連結)

CODE

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  // 先建立 table 初始值
  const table = [1, 2];
  // 處理 edge case
  if (n <= 2) {
    return table[n - 1];
  }
  // 採用 button-up 的方式，每階的抵達方式，皆為前兩階抵達方式之和。
  for (let i = 2; i < n; i++) {
    table.push(table[i - 1] + table[i - 2]);
  }
  return table[table.length - 1];
};

心得

這題一開始用暴力解，解到我有點吐血，後來也是只能多方參考其他大大的想法，並結合維基百科上的解說，才搞定這題，哈哈哈

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