JavaScriptで階段の登り方の総数を求めるアルゴリズム

問題の概要

次のような問題を考えてみましょう。

段数がnの階段があり、下に立っている人が最上部まで登ろうとしています。この人は一度に1段または2段ずつ登ることができます。このとき、頂上にたどり着く方法が何通りあるかを数える必要があります。

つまり、階段の段数nを受け取り、登り方の総数を計算して返すJavaScript関数を実装することが求められます。

解き方のポイント

この問題はフィボナッチ数列と密接な関係があります。n段目に到達するには、「(n-1)段目から1段登る」か「(n-2)段目から2段登る」かの2通りの選択肢しかないため、次の漸化式が成り立ちます。

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

この性質を利用すれば、直近2つの段の値だけを保持しながら順番に更新していくことで、余分なメモリを使わずに効率よく答えを求められます。

サンプルコード

以下が実装例です。

const recursiveStaircase = (num = 10) => {
    if (num <= 0) {
        return 0;
    }
    const steps = [1, 2];
    if (num <= 2) {
        return steps[num - 1];
    }
    for (let currentStep = 3; currentStep <= num; currentStep += 1) {
        [steps[0], steps[1]] = [steps[1], steps[0] + steps[1]];
    }
    return steps[1];
};
console.log(recursiveStaircase());
console.log(recursiveStaircase(4));
console.log(recursiveStaircase(13));

実行結果

コンソールには次のように出力されます。

89
5
377

コードの解説

この関数は以下の手順で動作します。

1. 初期チェック：引数numが0以下の場合は登り方が存在しないため、0を返します。
2. 小さなケースの処理：numが2以下の場合は、1段なら1通り、2段なら2通りであることが自明なので、配列stepsから直接値を返します。
3. 反復計算：3段目以降は、「前の段」と「前々の段」の値を足し合わせながら、分割代入によって配列内の2つの値を入れ替えて更新していきます。時間計算量はO(n)、追加のメモリはO(1)で済む非常に効率的な手法です。

例えば4段の階段の場合、登り方は「1+1+1+1」「1+1+2」「1+2+1」「2+1+1」「2+2」の5通りとなり、実行結果の5と一致します。同様に10段では89通り、13段では377通りとなります。