📘 題目敘述
你正在爬一個有 n 階的樓梯。每一次你可以選擇爬1 階 或 2 階。
請問總共有多少種不同的方法可以爬到樓梯頂端？
條件限制
0 ≤ n ≤ 45
🧠 解題思路
我在思考這題時，並不是直接想「要怎麼算最快」，而是先問自己一個最根本的問題：
如果我要走到第
n階，最後一步是怎麼來的？
這個問題一想清楚，整題的結構其實就已經出來了。
所有變數
n：樓梯的總階數（題目輸入）step：用來記錄「走到第 i 階的方法數」的陣列stair：目前正在計算的方法數所對應的階數top：最後要回傳的結果，也就是走到第n階的方法數
🪜 主要流程步驟
關鍵觀察：最後一步的來源
假設我要走到第 n 階，那最後一步只可能有兩種情況：
- 從第
n-1階走 1 步 上來 - 從第
n-2階走 2 步 上來
除此之外，不存在第三種可能。
也就是說：
- 所有「能走到第
n-1階的方法」，最後再走 1 步，都可以到n - 所有「能走到第
n-2階的方法」，最後再走 2 步，也可以到n
而這兩種來源 互不重疊，剛好涵蓋所有走法。
核心遞推關係
走到第 n 階的方法數 = 走到第 n-1 階的方法數 + 走到第 n-2 階的方法數
用符號表示就是：
step[n] = step[n-1] + step[n-2]
為什麼要先處理最小情況
在正式往上推之前，我會先確認最小的階數狀況：
n = 0
- 沒有階梯要爬
- 什麼都不做，也算是一種方法
n = 1
- 只能走 1 階
- 也只有一種方法
因此在我的邏輯中：
step[0] = 1step[1] = 1
這兩個值就是整個推導的起點。
為什麼這是一題動態規劃（DP）
整理完整體想法後，我發現這題完全符合 DP 的特徵：
- 大問題（走到第
n階）可以拆成小問題（n-1、n-2） - 子問題的結果會被反覆使用
- 有明確的狀態轉移關係
因此正確的做法不是暴力列出所有走法，而是：
- 從小的階數開始
- 把每一階的結果記錄下來
- 一路推到第
n階
和費波那契數列的關係
在寫完這題後，我也意識到：
- 這個遞推關係
- 這個初始條件
其實和 費波那契數列 是完全一樣的結構，只是題目換成了「爬樓梯」這個情境。
💻 程式碼實作
class Solution {
public:
int climbStairs(int n) {
vector<int> step = {1, 1};
int stair = 2;
int top;
if (n == 0 || n == 1) {
return 1;
}
while (stair <= n) {
step.push_back(step[stair - 1] + step[stair - 2]);
stair++;
}
top = step[n];
return top;
}
};