経路合計

問題

n段の階段を上がるときに、１ステップで１段、２段、３段のどれかであがれるときに考えられる上がり方の合計は？

考え方

n段目にはn-1段目から１段で、n−２段目からは2段、n-3段目には３段であがれる。 つまり、f(n) = f(n-1) + f(n-2) + f(n-3)である。 この場合の時間計算量はになる。

ただし、一度計算したものは利用できるはずなので、値を記録しておく。 すると時間計算量はO(n)になる。

注意として、n = 1に到達する経路を１、n = 0の時は０として考えています。

コード例

pythonで実装しました。 効率の悪い方

def countWays(n):
    if n==1:
        return 1
    elif n < 1:
        return 0
    return countWays(n-1) + countWays(n-2) +countWays(n-3)

計算結果を記録する方.numpy arrayは関数にポインタで渡されるので、他の関数で記録した値が参照できます。

import numpy as np

def countWays2(n):
    memo = np.zeros(n+1)
    def func(n, memo):
        if n==1:
            return 1
        elif n < 1:
            return 0
        if(memo[n]==0):
            memo[n] = func(n-1, memo) + func(n-2, memo) + func(n-3, memo)
        return memo[n]
    return func(n, memo)

実行結果は

if __name__ == "__main__":
    print(countWays(20))
    print(countWays2(20))

 > python code.py
66012
66012.0

です。