アルゴリズム概要

O(n)
時間計算量
O(1)
空間計算量
1 ≤ n ≤ 45
制約
Fibonacci DP
手法

問題文

n 段の階段を登ります。 毎回 1歩 または 2歩 だけ登れるとき、 頂上への 異なる登り方の総数 を返してください。

Example 1
入力: n = 2
出力: 2
1+1 / 2
Example 2
入力: n = 3
出力: 3
1+1+1 / 1+2 / 2+1
💡 問題の本質

n段目に到達するには 必ず 直前の2パターンから来る：
① (n-1)段目から1歩　② (n-2)段目から2歩
よって f(n) = f(n-1) + f(n-2) → フィボナッチ数列そのもの！

ステップバイステップ解説

フィボナッチ数列 インタラクティブ可視化

Python 実装

処理フローチャート

開始 入力受け取り n: int (1 <= n <= 45) n <= 2 ? Yes return n No 変数初期化 prev2 = 1 (f1) prev1 = 2 (f2) ループ残り > 0 ? Yes ローリング更新（タプル代入） prev2, prev1 = prev1, prev1 + prev2 ループバック No 結果を返す return prev1 → f(n) の値 終了 凡例 開始/終了 処理 条件 DP更新 出力 紫の矢印 = ループバック / 緑の矢印 = 成功パス / 赤の矢印 = 条件分岐

フローの説明：
1. 入力 n を受け取り、n ≤ 2 なら即 n を返す（基底条件）。
2. prev2=1, prev1=2 で初期化後、n-2 回ループで更新。
3. タプル代入 prev2, prev1 = prev1, prev1+prev2 で一時変数ゼロの安全なローリング更新。
4. ループ終了後に prev1（= f(n)）を返す。

計算量分析

アプローチ 時間計算量 空間計算量 備考
再帰（素朴） O(2ⁿ) O(n) n=45 で約35兆回呼び出し → TLE確定
メモ化再帰 @cache O(n) O(n) コールスタック + 辞書でヒープ消費
DP配列 (list) O(n) O(n) 直感的だが配列サイズnが無駄
✅ ローリング変数（採用） O(n) O(1) ★ 変数2個のみ・ヒープゼロ
定数テーブル O(1) O(1) n≦45限定。参照のみ。
📐 n=45 の結果値（オーバーフロー確認）
f(45) = 1,836,311,903
i32::MAX = 2,147,483,647 → ✅ 収まる
Python int = 任意精度 → ✅ オーバーフロー不要
f(46) = 2,971,215,073 > i32::MAX → ⚠️ C/Java/Rust では i64 が必要