プログラマ脳を鍛える数学パズル 15

10 段の階段があり、上と下から人が移動してくる。
一度に移動できるのは4段までという条件下で、同じ段に止まる手順は何通りあるか？

上と下の挟み撃ちではなくて、合計の移動量がジャスト 10 となるポイントを探すと読み替えた。
求められてるのが手順じゃなくて、パターン数のみなので、こうした方がメモ化のキャッシュ利用効率が上がるかなと思った。

N=10
memo = {}


def step_count(remain: int) -> int:
    if remain < 0:
        return 0
    if remain == 0:
        return 1

    if remain in memo:
        return memo[remain]

    counter = 0
    for u in range(1, 5):
        for d in range(1, 5):
            counter += step_count(remain - (u + d))

    memo[remain] = counter
    return counter

if __name__ == "__main__":
    print(step_count(N))