2026-09-14Hung-Chih Hsueh

主題: 學習筆記

LeetCode 70：爬樓梯，從重複遞迴到只保留前兩階

記錄我的 Climbing Stairs 解題過程，從排列組合誤區、指數時間遞迴，走到 O(n) 時間與 O(1) 額外空間的 rolling state。

這題看起來像排列組合。我一開始也往階乘走，後來才發現自己同時碰到兩個問題：相同步數不能當成彼此不同的物件排列，而且可能使用的 2 階步數不只一種。

接著我寫出正確的遞迴關係，卻在輸入變大後超時。問題出在執行方式：遞迴一直重算同一個答案。經過 AI 逐步講解與完整範例後，我把它重寫成只保存前兩階結果的版本。這篇保留三個階段，文章發布不代表我已經能在沒有提示時獨立重做。

題目

LeetCode 70：Climbing Stairs 給定一座有 n 階的樓梯，每次只能走 1 階或 2 階，要求計算抵達第 n 階共有多少種不同走法。步伐順序不同，視為不同走法。

例如 n = 3 時，可以走 1 + 1 + 1、1 + 2 或 2 + 1，共有 3 種。題目限制為 1 <= n <= 45。

我的第一個方向：用階乘計算排列

這是我最初卡住的版本。函式名稱與內容保留原本思路，只補上 TypeScript 型別。

function climbStairsFactorialAttempt(n: number): number {
    const isEven = n % 2 === 0;
    const howManyTwo = Math.floor(n / 2);

    function factorial(value: number): number {
        if (value < 0) return -1;

        let result = 1;
        for (let i = 1; i <= value; i++) {
            result *= i;
        }
        return result;
    }

    return factorial(howManyTwo * 2 + isEven ? 0 : 1);
}

TypeScript 會先因 number + boolean 拒絕這段運算式。在 JavaScript 中，它還有運算優先順序問題：條件運算子 ?: 的優先順序低於加法，所以參數實際上接近：

factorial((howManyTwo * 2 + isEven) ? 0 : 1);

只要條件轉成布林值後為真，就會呼叫 factorial(0)。這裡不能只靠補型別修正，因為計數方式本身也不完整。

即使補上括號，單一階乘仍然無法直接得到答案。以 n = 4 為例，合法走法包含：

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

這裡既有不同數量的 2，也有多個內容相同的 1。若使用組合數，需要分別計算每種 2 的數量再相加。這條路可以走，但比直接利用題目的前後關係更容易出錯。

我的第二版：關係正確，但重複計算

後來我找到這個遞迴：

function climbStairsRecursive(n: number): number {
    return ways(n);
}

function ways(n: number): number {
    return n <= 2 ? n : ways(n - 1) + ways(n - 2);
}

它的答案是對的。抵達第 n 階的最後一步，只可能是以下兩種情況：

從第 n − 1 階走 1 階上來。
從第 n − 2 階走 2 階上來。

兩組走法的最後一步不同，不會重複，也涵蓋了所有可能，因此：

ways(n) = ways(n - 1) + ways(n - 2)

問題出在執行方式。計算 ways(5) 時，ways(3) 會從不同分支重複出現；階數增加後，相同子問題會被重算很多次。這版時間的上界是 O(2ⁿ)，遞迴呼叫堆疊為 O(n)，所以不適合 n = 45。

我在完整教學後重寫的版本

遞迴式只依賴前一階與前兩階，不必保存整張表。以下是我理解 rolling state 後重新寫出的程式：

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

    let prev1 = 2;
    let prev2 = 1;
    let curr = 0;

    for (let i = 3; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return curr;
}

進入索引 i 的迴圈時：

prev1 是抵達第 i − 1 階的方法數。
prev2 是抵達第 i − 2 階的方法數。

先用兩個舊值算出 curr，再把狀態往前移。更新順序不能反過來；若先覆蓋 prev1，計算目前答案時就拿不到第 i − 1 階的舊值。

return curr 在這份程式中是安全的，因為 n 小於或等於 2 時已經提前回傳。若想讓回傳值直接對應「最後一個已完成狀態」，也可以回傳 prev1。對 n 大於或等於 3，兩者在迴圈結束時相同。

跟著 n = 5 走一次

初始狀態保存第 1 階與第 2 階的方法數：

i	prev2	prev1	curr
3	1	2	3
4	2	3	5
5	3	5	8

每一輪結束後，prev2 接手原本的 prev1，prev1 再接手剛算出的 curr。因此下一輪仍然保有需要的兩個前置答案。

另一條可行路徑：memoization

也可以保留遞迴，使用 Map 或陣列快取每個 ways(n)。這會把時間降為 O(n)，但仍需要 O(n) 快取與 O(n) 呼叫堆疊。

本題每個狀態只依賴前兩個狀態，所以 rolling state 使用更少空間。memoization 適合先驗證「重疊子問題」的觀察；rolling state 則是這題最後採用的版本。

正確性不變量

每次開始處理第 i 階時，prev1 與 prev2 分別保存第 i − 1 階和第 i − 2 階的方法數。

抵達第 i 階的每條路徑，依最後一步可分成「最後走 1 階」與「最後走 2 階」。前者的數量是 prev1，後者是 prev2，兩組互斥且沒有遺漏，所以 curr = prev1 + prev2 正確。

狀態更新後，prev1 保存第 i 階，prev2 保存第 i − 1 階，讓不變量在下一輪繼續成立。迴圈走到 n 後，保存的就是第 n 階答案。

複雜度

迴圈從 3 走到 n，每一輪只做固定次數的加法與指定，因此時間為 O(n)。程式只保存 prev1、prev2 與 curr，額外空間為 O(1)。

相較之下，第二版遞迴雖然程式短，卻有大量重複計算。Big O 描述的是工作量如何隨輸入成長，不是程式碼的行數。

可執行測試

我原本列出 n = 4 與兩次 n = 30。兩次相同案例不會增加覆蓋範圍，而且文字形式的 Output／Expected 也不會真的執行。改成 assertions 後，可以補齊基本狀態、第一輪迴圈與最大輸入：

import assert from "node:assert/strict";

assert.equal(climbStairs(1), 1);
assert.equal(climbStairs(2), 2);
assert.equal(climbStairs(3), 3);
assert.equal(climbStairs(4), 5);
assert.equal(climbStairs(5), 8);
assert.equal(climbStairs(30), 1346269);
assert.equal(climbStairs(45), 1836311903);

這份實作已用 n = 1 到 10、n = 30 與 n = 45 執行驗證。有限案例無法取代不變量，但能抓到初始值、迴圈範圍與更新順序常見的錯誤。

常見錯誤

把走法當成全部互異物件做階乘，忽略重複步數與不同的 2 階數量。
寫出正確遞迴式，卻沒有處理重疊子問題。
把 prev1 更新得太早，導致目前輪使用到新舊混合的資料。
只測 n = 4 或較大的數字，沒有涵蓋 n = 1、n = 2 與第一輪迴圈。
說空間是 O(1)，卻忽略遞迴呼叫堆疊。

這次學到的事

我真正需要記住的不是「爬樓梯等於費波那契數列」，而是如何從最後一步切開所有答案。最後走 1 階與最後走 2 階形成兩組互斥情況，遞推關係才有理由成立。

遞迴式只是狀態之間的關係，不代表一定要用遞迴執行。當目前狀態只需要前兩個結果時，可以把整棵重複展開的呼叫樹壓縮成兩個變數。這次有完整 AI 教學協助，下一次複習要在不看本文的情況下重新寫出不變量、程式與 assertions。

參考資料

LeetCode 70：Climbing Stairs：正式題意、範例與限制。
MDN：Operator precedence：第一版條件運算式的解析順序。
Node.js assert：可執行 assertions。