アルゴリズム勉強 #1 階段を登るのは何通り？をpythonで実装する

2021.10.23

こんにちは、独学ヒトリです。
アルゴリズムの勉強を始めます。最低週1回以上の更新を目指していきます。
今回は「階段を1段,2段,3段を1回で登れるとき、n段の階段を登る方法は何通り？」です。
再帰とメモ化について学びました。

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

再帰は時間かかる。次はメモ化

import sys
from functools import reduce
from operator import add

def getCountWaysMemo(n):
    if memo[n - 1] > 0: 
        return memo[n - 1]
    elif memo[n - 1] == 0:
        func_list = [getCountWaysMemo(n-k) for k in steps if n-k >= 1]
        memo[n - 1] = reduce(add, func_list)
        return memo[n - 1]

n = 20
memo = [1] + [0] * (n - 1)
steps = [1, 2, 3]
getCountWaysMemo(n)

学んだこと

メモ化すると、めっちゃ速い