from __future__ import annotations
from typing import Final


class Solution:
    """
    LeetCode 70 - Climbing Stairs

    1歩または2歩で n 段の階段を登る異なり数を返す。
    フィボナッチDP（ローリング変数・空間O(1)）を採用。

    Time Complexity:  O(n)
    Space Complexity: O(1)
    """

    def climbStairs(self, n: int) -> int:
        """
        Args:
            n: 階段の段数（制約: 1 <= n <= 45）

        Returns:
            頂上への異なる登り方の総数

        Raises:
            ValueError: n が制約範囲外の場合（業務利用時）
        """
        # --- 基底条件 ---
        # n=1: [1]       → 1通り
        # n=2: [1+1],[2] → 2通り
        if n <= 2:
            return n

        # --- ローリング変数で空間O(1)DP ---
        # prev2 = f(n-2), prev1 = f(n-1) として初期化
        prev2: int = 1  # f(1) = 1
        prev1: int = 2  # f(2) = 2

        # n-2 回更新: f(3) → f(4) → ... → f(n)
        for _ in range(n - 2):
            # タプル代入で右辺を先に評価（一時変数不要）
            prev2, prev1 = prev1, prev1 + prev2

        # ループ終了時: prev1 = f(n)
        return prev1

    # ------------------------------------------------------------------
    # 業務開発版（エラーハンドリング付き）
    # ------------------------------------------------------------------
    def climbStairs_production(self, n: int) -> int:
        """
        業務開発向け実装（型安全・エラーハンドリング重視）

        Args:
            n: 階段の段数

        Returns:
            頂上への異なる登り方の総数

        Raises:
            TypeError:  n が int でない場合
            ValueError: n が 1..45 の範囲外の場合
        """
        # 型チェック（bool は int のサブクラスなので除外）
        if not isinstance(n, int) or isinstance(n, bool):
            raise TypeError(f"n must be int, got {type(n).__name__}")

        # 範囲チェック
        MAX_N: Final[int] = 45
        if not (1 <= n <= MAX_N):
            raise ValueError(f"n must satisfy 1 <= n <= {MAX_N}, got {n}")

        # 基底条件
        if n <= 2:
            return n

        # ローリング変数DP（同実装）
        prev2: int = 1
        prev1: int = 2
        for _ in range(n - 2):
            prev2, prev1 = prev1, prev1 + prev2
        return prev1

# ❌ @cache メモ化再帰: O(n)空間・コールスタック消費
from functools import cache

@cache
def dp(i: int) -> int:
    if i <= 2: return i
    return dp(i-1) + dp(i-2)

# ❌ reduce: 可読性がやや低下（n<=45では速度差は無意味）
from functools import reduce
_, result = reduce(lambda acc, _: (acc[1], acc[0]+acc[1]), range(n-1), (1, 1))