AtCoder Beginner Contestの過去問を少しずつ解き始めたので、メモ。 DPの典型問題は手が勝手に動くくらい訓練しておきたい。
（※大したコードは書けていないので、この記事を参考にするのは推奨しません。）
N, M = map(int, input().split()) MOD = 1000000007 collapsed = [False for _ in range(N+1)] dp = [0 for _ in range(N+1)] # 0: 未到達orルートなし # ステップ崩壊地点を登録 for _ in range(M): a = int(input()) # 1-indexで定義する collapsed[a] = True # 初期化 dp[0] = 1 if not collapsed[1]: dp[1] = 1 for i in range(2, N+1): if collapsed[i]: continue # 剰余を求める計算は細かくやった方がメモリ＆計算時間の観点で有利 dp[i] = (dp[i-1] + dp[i-2]) % MOD # ans print(dp[N])
