題目連結(https://leetcode.com/problems/climbing-stairs/description)

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?

DP 與數學結合的有趣題目

1. Repeat（題目重複確認）

• 輸入：整數 n，表示有 n 階的階梯
• 輸出：走 n 層階梯的所有方法數
• 前提：1 <= n <= 45

2. Examples（舉例確認理解）

• n=1 方法數為1
  0->1
• n=2 方法數為2
  0->1->2
  0->2
• n=5 方法數為8
  0->1->2->3->4->5
  0->1->2 ->4->5
  0->1->2->3 ->5
  0->1 ->3 ->5
  0->1 ->3->4->5
  0 ->2->3->4->5
  0 ->2->3 ->5
  0 ->2 ->4->5
• 1, 1, 2, 3, 5, 8,…費波那契數列

3. Approach（解題思路）

方法 1：暴力解

• 每次決策都有兩種選擇，決策樹畫起來時間複雜度二的 n 次方，會有 stack overflow，無法實作
• 重複計算相同的子問題。比如在爬樓梯問題中，當我們在計算 dp(4) 時，會重複計算 dp(3) 和 dp(2)，這會使得算法的時間複雜度呈指數級增長，變得非常低效。
• 時間複雜度：O(2^n)
• 空間複雜度：O(n)

方法 2：一維 DP

• 建立 dp[i] 表示走到第 i 層的方式數
• 每一層的方法數都是前兩層的總和：dp[n] = dp[n-1] + dp[n-2]，因此最終問題可由子問題以 bottom-up 求解
• 用陣列 dp 紀錄 1~n 層的方法數，用 for loop 跑完即可得到 dp[n]
• 時間複雜度：O(n)
• 空間複雜度：O(n)

方法 3：一維 DP(改良版）

• 因為問題不用回傳 dp[0]~dp[n-1]，只需回傳 dp[n]，所以可用兩個變數來存就好，空間複雜度可以優化
• 時間複雜度：O(n)
• 空間複雜度：O(1)

4. Code（C++）

**#一維 DP**
class Solution{
public:
		int climbstairs(int n){
				if(n == 1) return 1;

				vector<int> dp(n+1);
				dp[1] = 1;
				dp[2] = 2;
				
				for(int i = 3; i <= n; i++){
					dp[i] = dp[i-1] + dp[i-2];
				}
				return dp[n];
		}
};

**#一維 DP(空間優化版）**
class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return 1;

        int dp1 = 1;
        int dp2 = 2;
        for(int i = 3 ; i <= n; i++){
            int temp = dp2;
            dp2 = dp1 + dp2;
            dp1 = temp;
        }
        return dp2;
    }
};

5. Test 範例

這題 test 不太用多解釋

n = 1 → 1 種走法
n = 2 → 2 種走法 (1+1, 2)
n = 3 → 3 種走法 (1+1+1, 1+2, 2+1)
n = 5 → 8 種走法

6. 相關題目與延伸概念

746. Min Cost Climbing Stairs

7. 補充：語法＆注意事項

1. 迴圈索引

   • for(int i = 3; i <= n; i++)

     不要寫成 i < n 或 dp[n] = ...，會造成錯誤。

2. 空間優化

   • 不需要整個 dp 陣列，用兩個變數即可。

3. 邊界條件

   • n = 1, n = 2 時需要特別處理。

ps. 部分內容經 AI 協助整理