先看沒有A的case，然後分別看最後一個是LorP的組合數做DP
最後就乘乘加加
然後幹你娘
我一開始寫mod = 1e9+7
怎麼用都錯 然後都跟答案差那一點點 就感覺很莫名奇怪
才發現1e9+7是float有誤差
要寫10**9+7才會對
我真的是幹==
害我一直在算式裡到處亂加mod 瞎猜到底是哪裡錯
所以我的code裡面一堆mod 好白癡
幹 還我時間==
超級姆咪
def checkRecord(self, n: int) -> int:
if n == 1:
return 3
elif n == 2:
return 8
# mod = 1e9+7
mod = 10**9+7
dp_L = [0 for _ in range(n+1)] # LP only
dp_P = [0 for _ in range(n+1)] # LP only
dp_L[1] = 1
dp_P[1] = 1
dp_L[2] = 2
dp_P[2] = 2
for i in range(3, n+1):
dp_L[i] = ((dp_P[i-2]*2)%mod + dp_L[i-2]) % mod
dp_P[i] = (dp_P[i-1] + dp_L[i-1]) % mod
dp_LP = [(i+j)%mod for i,j in zip(dp_L,dp_P)]
dp_LP[0] = 1
ans = dp_LP[n] # 0A
for i in range(1,n+1):
ans = (ans + (dp_LP[i-1]*dp_LP[n-i])%mod)%mod #1A
return ans