LeetCode 70: Climbing Stairs

基本資料

#

難易度: easy 第一次嘗試：2026-04-20 來源：Day 9 learning note

學習脈絡

#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

當天筆記摘錄

#

LC 70 - Climbing Stairs

#

• Status: Completed.
• Pattern: Fibonacci-style 1D DP.

State

#

dp[i] = number of distinct ways to reach step i

Base Case

#

dp[0] = 1
dp[1] = 1

dp[0] = 1 means there is one way to start before taking any steps: do nothing.

Transition

#

dp[i] = dp[i - 1] + dp[i - 2]

To reach step i, the last move must come from step i - 1 with one step or from step i - 2 with two steps.

Complexity

#

Time: O(n)
Space: O(n) with array, O(1) with two variables

整理補充

#

這題不要只說「就是 Fibonacci」。比較穩的說法是：dp[i] 是到第 i 階的 ordered step sequences 數量。最後一步只可能從 i - 1 走 1 階，或從 i - 2 走 2 階，所以兩個來源互斥，可以相加。提交版用 n <= 2 處理小 case，後面用兩個變數滾動同一個 recurrence。

正確解法

#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for _ in range(3, n + 1):
            prev2, prev1 = prev1, prev1 + prev2
        return prev1

複雜度

#

Time O(n), Space O(1).

要特別避免的錯誤

#

• Off-by-one base cases.
• Thinking order does not matter; sequences of 1/2 steps are distinct.

面試口說整理

#

我會把這題講成 ordered step sequences 的 counting DP。dp[i] 是站在第 i 階的方法數；最後一步只能從 i - 1 或 i - 2 來，所以把兩個 predecessor 的方法數相加，最後用兩個變數壓縮空間。