C++で階段の登り方の総数を求めるアルゴリズムを解説

問題の概要

n段の階段があり、ある人が1段目からn段目まで登ることを考えます。このとき「一度に登れる最大段数」も与えられます。これらの情報をもとに、n段目まで登る方法が何通りあるかを求めるのが本問題の目的です。

例えば、一度に最大2段まで登れるとしましょう。この場合、漸化式を立てることで問題を解くことができます。n段目に到達するには、(n-1)段目から1段登るか、(n-2)段目から2段登るかのどちらかしかありません。したがって、次の漸化式が成り立ちます。

ways(n) = ways(n-1) + ways(n-2)

例として、階段が10段、一度に登れる最大段数が2段である場合、登り方の総数は89通りとなります。

アルゴリズムの手順

この問題は動的計画法（ボトムアップ方式）を使えば効率的に解けます。手順は以下のとおりです。

• 階段の段数と同じサイズの配列 count を定義する
• count[0] := 1 とする（0段または1段の場合、登り方は1通り）
• i を 2 から stair-1 まで繰り返す
  • count[i] := 0 で初期化
  • j を 1 から i まで、かつ j ≤ max の範囲で繰り返す
    • count[i] := count[i] + count[i-j]
• count[stair-1] を返す

このアルゴリズムは、フィボナッチ数列と同じ構造を持っており、各段への登り方の数を小さい段から順に累積していくことで、重複計算を避けながら答えを求められます。計算量は O(n × max) です。

C++での実装例

#include<iostream>
using namespace std;
int stairClimbWays(int stair, int max){
    int count[stair]; // 結果をボトムアップ方式で計算
    count[0] = 1; // 0段または1段の場合、登り方は1通り
    count[1] = 1;
    for (int i=2; i<stair; i++){ // 2段目以降を順に計算
        count[i] = 0;
        for(int j=1; j<=max && j<=i; j++)
            count[i] += count[i-j];
    }
    return count[stair-1];
}
int countWays(int stair, int max){ // 一度に1段、2段、…max段まで登れる
    return stairClimbWays(stair+1, max);
}
int main (){
    int stair, max;
    cout << "Enter number of stairs: "; cin >> stair;
    cout << "Enter max stair a person can climb: "; cin >> max;
    cout << "Number of ways to reach: " << countWays(stair, max);
}

入力例

Stairs = 10
Max stairs a person can climb: 2

出力例

Enter number of stairs: 10
Enter max stair a person can climb: 2
Number of ways to reach: 89

まとめ

階段の登り方の総数を求める問題は、漸化式と動的計画法を組み合わせることで、シンプルかつ効率的に解くことができます。max の値を変えれば、一度に3段以上登れるケースにも柔軟に対応できるのがこの実装の利点です。再帰を使う方法と比べて計算量を大幅に抑えられるため、実務においても有用なアプローチといえます。