LeetCode 70：爬樓梯 — 動態規劃經典入門

題目描述

你正在爬一個有 n 階的樓梯。每次你可以爬 1 階或 2 階。請問有多少種不同的方法可以爬到樓頂？

範例：

輸入: n = 2
輸出: 2 (1+1, 2)

輸入: n = 3
輸出: 3 (1+1+1, 1+2, 2+1)

解題思路

這是斐波那契數列的變體。設 dp[i] 為爬到第 i 階的方法數，則：

• dp[1] = 1
• dp[2] = 2
• dp[i] = dp[i-1] + dp[i-2] (i ≥ 3)

因為只依賴前兩項，可用兩個變量滾動更新，將空間優化至 O(1)。

參考代碼 (C++)

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1;
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

複雜度分析

• 時間複雜度：O(n) —— 單層循環。
• 空間複雜度：O(1) —— 僅使用常數變量。