iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 15
0
自我挑戰組

[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ系列 第 15

[LeetCode with JavaScript] Day 15: Climbing Stairs

觀前提醒:

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

題目

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];
};

心得

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


謝謝大家的收看,LeetCode 小學堂我們下次見~/images/emoticon/emoticon29.gif


上一篇
[LeetCode with JavaScript] Day 14: Maximum Subarray
下一篇
[LeetCode with JavaScript] Day 16: Fizz Buzz
系列文
[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言