ZeroJudge 解題筆記：d212. 東東爬階梯

作者：王一哲
日期：2025年8月25日


ZeroJudge 題目連結：d212. 東東爬階梯

解題想法

先找規律，假設走到第 $i$ 階的走法存在表格 $dp[i]$ 之中。

1. 走到第 0 階、第 1 階，只有一種走法，即 $dp[0] = 1, dp[1] = 1$。
2. 走到第 2 階，可以先走到第 1 階再往上走 1 階，也可以從第 0 階直接往上走 2 階，有 2 種走法，即 $dp[2] = dp[1] + dp[0] = 2$。
3. 走到第 3 階，可以先走到第 2 階再往上走 1 階，也可以先走到第 1 階直接往上走 2 階，有 3 種走法，即 $dp[3] = dp[2] + dp[1] = 3$。
4. 走到第 4 階，可以先走到第 3 階再往上走 1 階，也可以先走到第 2 階直接往上走 2 階，有 5 種走法，即 $dp[4] = dp[3] + dp[2] = 5$。
5. 走到第 $i$ 階，可以先走到第 $i-1$ 階再往上走 1 階，也可以先走到第 $i-2$ 階直接往上走 2 階，即 $dp[i] = dp[i-1] + dp[i-2]$。

看到這裡應該已經發現了，答案就是費氏數列。因為這題有多筆測資，而且題目範圍不大，最多到 99 階，所以先建表算出走到第 0 階至走到第 99 階的走法，讀取一個數量 $n$ 之後再查表找答案，這樣會比較快。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

dp = [0]*100  # 建表，內容為走到指定階數的走法
dp[0] = dp[1] = 1  # 第 0 階、第 1 階，只有一種走法
for i in range(2, 100): dp[i] = dp[i-1] + dp[i-2]  # 第 2 階開始，走法等於前兩項的和

for n in sys.stdin: print(dp[int(n)])  # 讀取 n 代入 dp 找答案

C++ 程式碼

要開 long long 才不會溢位，使用時間約為 1 ms，記憶體約為 68 kB，通過測試。

#include <cstdio>
typedef long long LL;
using namespace std;

int main () {
    LL dp[100] = {0};  // 建表，內容為走到指定階數的走法
    dp[0] = 1; dp[1] = 1;  // 第 0 階、第 1 階，只有一種走法
    for(int i=2; i<100; i++) dp[i] = dp[i-1] + dp[i-2];  // 第 2 階開始，走法等於前兩項的和
    int n;
    while(scanf("%d", &n) != EOF) printf("%lld\n", dp[n]);  // 讀取 n 代入 dp 找答案
    return 0;
}