問題の定式化

段数が n の階段を登る際、一度に1段または2段ずつ飛んで進行します。この移動規則に従い、最終段に到達するまでの全経路パターン数を計算するアルゴリズムについて解説します。

アプローチ1：数学的組合せによる求解

組合せ数学の応用では、1段ジャンプを s 回、2段ジャンプを d 回実施した場合の制約式 s + 2d = n に着目します。具体的な回数組合せが確定すれば、その順序を含む総経路数は二項係数 (s+d)! / (s! × d!) で導出可能です。可能な d の範囲をループで走査し、対応する s を算出して組合せ値を累積することで解を得ます。階乗演算は再帰呼び出しによるスタック枯渇を防ぐため、反復処理で実装しています。

#include <stdio.h>

// 階乗を計算する関数
long long factorial(int x) {
    if (x <= 1) return 1;
    long long res = 1;
    for (int k = 2; k <= x; k++) {
        res *= k;
    }
    return res;
}

// 指定された1歩目と2歩目の回数に対するパターン数を算出
long long get_combination_paths(int single, int double_) {
    int total = single + double_;
    return factorial(total) / (factorial(single) * factorial(double_));
}

// メインアルゴリズム：組合せ理論に基づき総パターン数を累積
long long count_ways_combinatorial(unsigned int steps) {
    long long total_patterns = 0;
    for (int d = 0; d <= steps / 2; d++) {
        int s = steps - (d * 2);
        total_patterns += get_combination_paths(s, d);
    }
    return total_patterns;
}

int main() {
    unsigned int n;
    if (scanf("%u", &n) == 1) {
        printf("%lld\n", count_ways_combinatorial(n));
    }
    return 0;
}

アプローチ2：状態遷移の反復計算

再帰的な状態分解の特性を利用する場合、目標の n 段目への到着経路は、直前の (n-1) 段目と (n-2) 段目からの遷移に完全に分割できます。これは斐波那契数列の漸化式と同型ですが、素朴な再帰呼び出しでは同一計算が重複実行され計算量が指数関数的に増大します。そのため、前方の状態値を保持しながら逐次更新する反復的动态計画法（DP）へ構造を変更し、線形時間 O(n) で高精度な値を算出する構成としています。

#include <stdio.h>

// 反復的动态計画法による状態遷移の最適化計算
long long solve_staircase_dp(unsigned int target) {
    if (target == 1) return 1;
    if (target == 2) return 2;

    long long prev = 1; // 1手前の段階における累積パターン数
    long long curr = 2; // 現在の段階における累積パターン数
    long long next_val = 0;

    for (unsigned int i = 3; i <= target; i++) {
        next_val = prev + curr;
        prev = curr;
        curr = next_val;
    }
    return curr;
}

int main() {
    unsigned int n;
    if (scanf("%u", &n) == 1) {
        printf("%lld\n", solve_staircase_dp(n));
    }
    return 0;
}