前言

今天我們來挑戰的是 Climbing Stairs（爬樓梯）這道題目！想像一下，你站在樓梯的底部，目標是爬到最頂端，每次可以選擇走一步或兩步。問題是：有多少種不同的方法可以爬到最頂端呢？這是不是讓人聯想到排列組合？別擔心，這個問題其實可以用簡單的數學方法來解決～那我們就一起來看看怎麼解吧！

英文題目 Climbing Stairs

難度：Easy

題目描述：

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

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

你正在爬樓梯，樓梯總共有 n 階。每次你可以選擇爬 1 階或 2 階，問到達頂端有多少種不同的方式？

範例 1：

輸入： n = 2

輸出： 2

Explanation: There are two ways to climb to the top.
解釋： 有兩種方法可以爬到頂端：

1. 1 步 + 1 步
2. 2 步

範例 2：

輸入： n = 3

輸出： 3

Explanation: There are three ways to climb to the top.
解釋： 有三種方法可以爬到頂端：

1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步

思路

這道題其實是典型的斐波那契數列問題。每次我們可以選擇走 1 步或 2 步，因此要爬到第 n 階的方法數等於爬到第 n-1 階和爬到第 n-2 階的方法數之和。

具體來說：

• 如果你想爬到第 n 階，你可以從第 n-1 階爬 1 步上去，或者從第 n-2 階爬 2 步上去。
• 這樣我們可以得到一個遞迴關係：f(n) = f(n-1) + f(n-2)，其中 f(n) 代表爬到第 n 階的方法數。

我們可以用兩種方法來解這個問題：

1. 遞迴（但效率不高）。
2. 動態規劃：透過記錄之前的結果來優化。

這裡我們採用動態規劃的方法，能夠在 O(n) 的時間內解決問題，並且只需要常數級別的額外空間。

詳細步驟

1. 初始化：我們知道：

   • 如果樓梯只有 1 階，那麼只有 1 種方法可以爬到頂端。
   • 如果樓梯有 2 階，則有 2 種方法可以爬到頂端（1+1 和 2）。

2. 動態規劃：我們用兩個變數 a 和 b 分別記錄爬到 n-1 和 n-2 階的方法數，然後從第 3 階開始，逐步計算每一階的方法數，直到第 n 階。

3. 最後結果：計算到第 n 階時，b 就是我們想要的結果。

實作

function climbStairs(n: number): number {
    if (n <= 2) return n;

    let a = 1; // 爬到第 1 階的方法數
    let b = 2; // 爬到第 2 階的方法數

    for (let i = 3; i <= n; i++) {
        const temp = a + b; // 爬到第 i 階的方法數
        a = b; // 更新 a 為前一階的方法數
        b = temp; // 更新 b 為當前階的方法數
    }

    return b; // 返回爬到第 n 階的方法數
}

解題心法

1. 動態規劃的應用：

   • 我們可以發現，爬到第 n 階的方法數與爬到前兩階的方法數有關，這是一個典型的動態規劃問題。通過記錄之前的結果，我們可以在 O(n) 的時間內計算出結果。

2. 優化空間複雜度：

   • 我們不需要開一個陣列來存儲每階的方法數，只需用兩個變數 a 和 b 來記錄爬到 n-1 和 n-2 階的方法數即可，這樣可以將空間複雜度優化到 O(1)。

3. 斐波那契數列的應用：

   • 這道題的解法實際上就是計算斐波那契數列，因此掌握這個數列的遞迴關係對解這道題非常關鍵。

為什麼這樣處理？

這種方法利用了動態規劃的思想，能夠避免重複計算，將時間複雜度壓縮到 O(n)，並且只用了常數級別的空間來儲存中間結果，非常高效。

本次要點：

• 遞迴關係：爬到第 n 階的方法數等於爬到 n-1 階和 n-2 階的方法數之和。
• 動態規劃：透過儲存前兩個結果來計算當前的結果，避免重複計算。
• 時間和空間複雜度：時間複雜度為 O(n)，空間複雜度為 O(1)。

這道題是不是讓人聯想到爬樓梯的過程呢？每一步都建立在前一步和再前一步的基礎上～希望這個動態規劃的解法能幫助你輕鬆解題，並應用到更多類似的問題中！我們下次再來挑戰更多有趣的題目吧！🚶‍♂️🚶‍♀️