プログラマ脳を鍛える数学パズル 15
10 段の階段があり、上と下から人が移動してくる。
一度に移動できるのは4段までという条件下で、同じ段に止まる手順は何通りあるか?
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/14
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (11件) を見る
上と下の挟み撃ちではなくて、合計の移動量がジャスト 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))