DP 01: 爬樓梯問題 (Climbing Stairs)

題目描述

假設你正在爬樓梯。需要 n 階才能到達樓頂。

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

思路解析

這是一個經典的動態規劃 (Dynamic Programming) 問題。

我們可以這樣思考：

• 要到達第 i 階，只能從第 i-1 階爬 1 步，或是從第 i-2 階爬 2 步而來。
• 因此，到達第 i 階的方法數 dp[i] 等於到達第 i-1 階的方法數加上到達第 i-2 階的方法數。

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

這其實就是費氏數列 (Fibonacci Sequence)。

C++ 實作

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

複雜度分析

• 時間複雜度: $O(n)$
• 空間複雜度: $O(1)$