n段目の階段に到達する方法の数を求めるアルゴリズム

問題の概要

n段の階段があり、ある人は1段目からn段目まで登ろうとしています。一度に登れる最大段数も与えられているものとします。これらの情報をもとに、n段目の階段に到達する方法が何通りあるかを求めるのがこの問題です。

たとえば、一度に最大2段まで登れる場合を考えてみましょう。この問題は再帰的な関係（漸化式）を使って解くことができます。n段目に到達するには、(n-1)段目から1段登るか、(n-2)段目から2段登るかのいずれかしかありません。したがって、次の漸化式が成り立ちます。

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

これは有名なフィボナッチ数列と同じ構造です。実際、一度に最大2段まで登れる場合、到達方法の数はフィボナッチ数列と一致します。

入力と出力

入力は「階段の段数」と「一度に登れる最大段数」の2つです。たとえば段数が10、最大段数が2の場合、答えは89通りになります。

入力：
階段の段数（例：10）、一度に登れる最大段数（例：2）

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

アルゴリズム

動的計画法（ボトムアップ方式）を用いて、各段に到達する方法の数を下の段から順に計算していきます。

関数：stairClimbWays(stair, max)

入力：階段の段数、一度に登れる最大段数

出力：n段目に到達する方法の数

Begin
    define array count of size same as stair number
    count[0] := 1
    count[1] := 1

    for i := 2 to stair - 1, do
        count[i] := 0
        for j = 1 to i and j <= max, do
            count[i] := count[i] + count[i - j]
        done
    done
    return count[stair - 1]
End

配列countのi番目には「i段目に到達する方法の数」が格納されます。i段目へは、直前のmax段以内の各段（i-j段目）から登ってくることができるため、それらの段に至る方法の数をすべて足し合わせます。

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〜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);
}

実行結果

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

計算量

時間計算量はO(n × max)です。各段について最大max回の加算を行うためです。空間計算量は結果を格納する配列の分だけ必要となり、O(n)となります。単純な再帰で解くと同じ計算を何度も繰り返して指数時間かかりますが、この動的計画法によるアプローチなら効率的に求められます。