ABC129 C - Typical Stairs
https://atcoder.jp/contests/abc129/tasks/abc129_c
提出
code: python
n, m = map(int, input().split())
a = int(input()) for _ in range(m)
dp = []
steps =1, 2
now = 0
解答
code: python
n, m = map(int, input().split())
a = int(input()) for _ in range(m)
broken = [[] for _ in range(n+1)]
for i in a:
brokeni = 1
# 1つ多めに取る
dp = 0 for _ in range(n+2)
mod = 1000000007
# 最上段
dpn = 1
# 最上段より1つ下の段から順に下っていく
for i in range(n-1, -1, -1):
if brokeni:
dpi = 0
continue
dpi = (dpi+1 + dpi+2)
print(dp0 % mod)
テーマ
#dp
提出
AC
code: python
n, m = list(map(int, input().split()))
a = int(input()) for _ in range(m)
a = set(a)
# 0 1 2 3 4 5 6
# . x
# dp2 = (dp1) + (dp0)
# dp4 = (dp2)
# dp5 = (dp4)
# dp6 = (dp5) + (dp4)
mod = 1000000007
dp = 0 * (n+1)
dp0 = 1
if 1 not in a:
dp1 = dp0
else:
dp1 = 0
for i in range(2, n+1):
if i - 1 not in a:
dpi += dpi-1
if i - 2 not in a:
dpi += dpi-2
print(dpn % mod)