Pythonで階段の登り方の総数を求めるプログラムを作成する方法

プログラミングの典型的な問題として、「階段の登り方」問題があります。この記事では、Pythonを使ってこの問題を動的計画法（DP）で解く方法を詳しく解説します。

問題の概要

n段の階段があるとします。一度に1段または2段ずつ上ることができる場合、この階段を上るユニークな登り方の総数を返す関数を定義する必要があります。

ポイントは、段を踏む順序が異なれば別の登り方としてカウントするという点です。また、答えが非常に大きな数になる可能性があるため、結果を 10^9 + 7 で割った余りを返します。

例えば、入力が n = 5 の場合、出力は 8 となります。これは、次の8通りのユニークな登り方が存在するためです。

• 1, 1, 1, 1, 1
• 2, 1, 1, 1
• 1, 2, 1, 1
• 1, 1, 2, 1
• 1, 1, 1, 2
• 1, 2, 2
• 2, 1, 2
• 2, 2, 1

解法のアプローチ：動的計画法（DP）

この問題はフィボナッチ数列と同じ構造を持っています。i 番目の段に到達する方法の数は、「i-1 番目から1段で来る方法」と「i-2 番目から2段で来る方法」の合計になります。以下の手順で解きます。

1. サイズ n+1 の配列 dp を作成し、すべて0で初期化する
2. dp[1] = 1 を設定する（1段目への登り方は1通り）
3. i = 2 から n+1 まで繰り返し処理を行い、dp[i] = dp[i-1] + dp[i-2] を計算する
4. 配列 dp の最後の要素を m で割った余りを返す

実装例

それでは、実際のPythonコードを見てみましょう。

m = (10**9) + 7
class Solution:
    def solve(self, n):
        dp = [0 for _ in range(n+2)]
        dp[1] = 1
        for i in range(2, n+2):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1] % m

ob = Solution()
print(ob.solve(5))

入力

5

出力

8

まとめ

このように、階段の登り方の総数を求める問題は、動的計画法を用いることで効率的に解くことができます。時間計算量はO(n)、空間計算量もO(n)であり、n段の階段に対して線形時間で計算可能です。この手法は、フィボナッチ数列に関連するさまざまな組み合わせ最適化問題にも応用できるので、ぜひ覚えておきましょう。