LeetCode - Climbing Stairs（爬樓梯）

題目描述

假設你正在爬一個樓梯。需要 n 步才能到達樓頂。每次你可以爬 1 或 2 步。問有多少種不同的方法可以爬到樓頂？

範例：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到頂端。
1. 1 步 + 1 步
2. 2 步

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到頂端。
1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步

限制：

• 1 <= n <= 45

解法思路

這是一個典型的斐波那契數列問題。對於 n 步到達頂樓的方法數 f(n)，可以由 f(n-1)（最後一步走了 1 步）和 f(n-2)（最後一步走了 2 步）兩種情況得出，因此有遞推公式：

[ f(n) = f(n-1) + f(n-2) ]

初始條件

• 當 n = 1 時，只有一種方式：f(1) = 1
• 當 n = 2 時，有兩種方式：f(2) = 2

代碼實現

可以使用動態規劃或空間優化的方式來實現。由於僅需要前兩項的數據來計算下一步，我們可以進行空間優化，僅用兩個變量來儲存狀態。

Python 實現

def climbStairs(n):
    if n <= 2:
        return n

    first, second = 1, 2
    for i in range(3, n + 1):
        third = first + second
        first = second
        second = third

    return second

代碼解析

1. 當 n <= 2 時，直接返回 n，因為步數與方法數相等。
2. 從第 3 階開始，不斷計算 third 為 first + second 的和，並向前推進。
3. 最終 second 即為 f(n)。

時間和空間複雜度

• 時間複雜度：O(n)，需要遍歷 n 步。
• 空間複雜度：O(1)，只使用了常數空間來存儲狀態。