問題概要と考察

この問題では、n段の階段を1段または2段ずつ登る場合の、登り方の総数を求める必要があります。各段数における解を観察すると、フィボナッチ数列と同じパターンに従っていることが分かります。

• 1段：1通り
• 2段：2通り（1+1 または 2）
• 3段：3通り（1+1+1、1+2、2+1）
• 4段：5通り（1+1+1+1、1+1+2、1+2+1、2+1+1、2+2）

つまり、n段目までの登り方の総数は(n+1)番目のフィボナッチ数に該当します。

【アプローチ1】再帰による実装

シンプルな再帰関数を用いた実装です。ただし、この方法では計算量が指数関数的に増加するため、実用性は低いです。

def count_ways(n):
    if n == 0 or n == 1:
        return 1
    return count_ways(n - 1) + count_ways(n - 2)

step = int(input("段数を入力してください: "))
print(count_ways(step))

【アプローチ2】メモ化付き再帰

すでに計算済みの結果を保存することで、無駄な計算を省くことができます。

def count_ways_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n == 0 or n == 1:
        return 1
    if n not in memo:
        memo[n] = count_ways_memo(n - 1, memo) + count_ways_memo(n - 2, memo)
    return memo[n]

step = int(input("段数を入力してください: "))
print(count_ways_memo(step))

【アプローチ3】動的計画法（DP）による実装

配列を使わず、2つの変数だけを使ってフィボナッチ数列を逐次計算します。

def count_ways_dp(n):
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return a

step = int(input("段数を入力してください: "))
print(count_ways_dp(step))

【アプローチ4】行列の高速べき乗による解法

高速な行列累乗アルゴリズムを用いて、フィボナッチ数列の第n項を効率よく求めます。

def multiply_matrix(a, b):
    return [[a[0][0]*b[0][0] + a[0][1]*b[1][0],
             a[0][0]*b[0][1] + a[0][1]*b[1][1]],
            [a[1][0]*b[0][0] + a[1][1]*b[1][0],
             a[1][0]*b[0][1] + a[1][1]*b[1][1]]]

def matrix_power(matrix, n):
    result = [[1, 0], [0, 1]]  # 単位行列
    while n > 0:
        if n % 2 == 1:
            result = multiply_matrix(result, matrix)
        matrix = multiply_matrix(matrix, matrix)
        n //= 2
    return result

def count_ways_matrix(n):
    if n == 0 or n == 1:
        return 1
    matrix = [[1, 1], [1, 0]]
    power = matrix_power(matrix, n - 1)
    return power[0][0]

step = int(input("段数を入力してください: "))
print(count_ways_matrix(step))