LeetCode 70題 Climbing Stairs 解題筆記

題目描述
你正在爬樓梯，需要
n
步才能到達頂端。
每次你可以爬
1 或 2 步
。
請問你有多少種不同的方法可以爬到頂端？
範例
範例 1：
輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到頂端：
1 步 + 1 步
2 步
範例 2：
輸入：n = 3
輸出：3
解釋：有三種方法可以爬到頂端：
1 步 + 1 步 + 1 步
1 步 + 2 步
2 步 + 1 步
Constraints
1 <= n <= 45
解題思路
這題是典型的
動態規劃 (DP)
題目。
定義
dp[i]
表示爬到第
i
階的方法數。
狀態轉移方程：
[
dp[i] = dp[i-1] + dp[i-2]
]
因為到第 i 階可以從 i-1 或 i-2 走一步到達。
初始化：
dp[1] = 1
(只有一種方法爬到第一階)
dp[2] = 2
(兩種方法爬到第二階：1+1 或 2)
遞迴或迴圈都可以實作。
範例解題 - 範例一
以 “9” 格樓梯作為例，我們可以用
DP 表
來表示爬到每一階的方法數：
i (階數)
1
2
3
4
5
6
7
8
9
dp[i]
1
2
3
5
8
13
21
34
55
表格說明：
dp[1] = 1
：爬到第 1 階只有 1 種方法 →
[1]
dp[2] = 2
：爬到第 2 階有 2 種方法 →
[1+1], [2]
dp[i] = dp[i-1] + dp[i-2]
：第 i 階可以從 i-1 階走 1 步或從 i-2 階走 2 步，因此方法數相加。
每階方法拆解
爬到第 1 階：
方法數：1
拆解：
[1]
爬到第 2 階：
方法數：2
拆解：
[1 + 1]
[2]
爬到第 3 階：
方法數：3 (
dp[3] = dp[2] + dp[1] = 2 + 1
)
拆解：
從第 2 階走 1 步：
[1 + 1] + 1 = [1 + 1 + 1]
從第 1階走 2 步：
[1] + 2 = [1 + 2]
從第 1階走 2 步（另一種順序）：
[2] + 1 = [2 + 1]
爬到第 4 階：
方法數：5 (
dp[4] = dp[3] + dp[2] = 3 + 2
)
拆解：
從第 3 階走 1 步：
[1+1+1] + 1 = [1+1+1+1]
[1+2] + 1 = [1+2+1]
[2+1] + 1 = [2+1+1]
從第 2 階走 2 步：
[1+1] + 2 = [1+1+2]
[2] + 2 = [2+2]
爬到第 5 階：
方法數：8 (
dp[5] = dp[4] + dp[3] = 5 + 3
)
拆解：
從第 4 階走 1 步：
[1+1+1+1]+1, [1+2+1]+1, [2+1+1]+1, [1+1+2]+1, [2+2]+1
從第 3 階走 2 步：
[1+1+1]+2, [1+2]+2, [2+1]+2
爬到第 6 階：
方法數：13 (
dp[6] = dp[5] + dp[4] = 8 + 5
)
拆解：
從第 5 階走 1 步：將 dp[5] 每種方法加上 1
從第 4 階走 2 步：將 dp[4] 每種方法加上 2
依此類推，直到第 9 階，最終：
dp[9] = 55
表示爬 9 階樓梯總共有
55 種不同方法
小結
每階方法數 = 上一階 + 上二階的方法數。
DP 表格可以快速查出任意階的總方法數。
參考程式碼（C++ 範例）

class Solution
{
public:
    int Stairs(int n, int dp[])
    {
        // 特殊情況：當 n = 3 時，直接計算 dp[3] = dp[1] + dp[2]
        if (n == 3)
        {
            dp[3] = dp[1] + dp[2];
            return dp[3];
        }

        // 遞迴呼叫計算前一階的方法數，確保 dp[n-1] 已計算
        Stairs(n - 1, dp);

        // 第 n 階的方法數 = 前一階 + 前兩階的方法數
        dp[n] = dp[n - 1] + dp[n - 2];

        return dp[n]; 
    }

    int climbStairs(int n)
    {
        // 初始陣列50格 因為題目只限制到45 開50不多不少
        int dp[50] = {0};
        // 初始化 一格 兩格
        dp[1] = 1;
        dp[2] = 2;
        if (n <= 2)
        {
            return dp[n];
        }
        Stairs(n, dp);
        return dp[n];
    }
};

---

## 複雜度分析
- **時間複雜度**：O(n)
- **空間複雜度**：O(1)

---

## LeetCode 成績
- Runtime：0 ms — Beats 100% of C++ users
- Memory：7.85 MB — Beats 73.07% of C++ users
---

## 補充說明

我的解法不一定是最佳解，  
但我會盡可能去思考、調整，  
朝著最佳解的方向努力。  
如果有想要補充的歡迎在下面評論區補充歐 !