<AtCoder Python 茶色>動的計画法の計算量
解決したいこと
こちらの問題を動的計画法を用いて以下の方法でやると計算量はО(N)になると思ったのですが、TLEになってしまいます。
該当するソースコード
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
dp = [-1] * (n+1)
dp[0] = 0
def rep(i):
if i == 0:
return 1
#場合分けの重複を回避
if dp[i] != -1:
return dp[i]
result = 0
if i-1 not in a and i-1 >= 0:
result += rep(i-1)
if i-2 not in a and i-2 >= 0:
result += rep(i-2)
dp[i] = result
return result
print(rep(n) % (10**9+7))
0
