競賽放棄的那一題
dp維度開在 (idx in [0,N), previous的選擇, 目前贏幾場)
一開始用@lru_cache()還不行
要用@cache
我也不知道差哪裡 buffer size 有這麼容易爆ㄇ==
而且系統分析我這個是O(3^N)
但我覺得是O(N^2)ㄚ==
確實跑不快就是了
久到我以為要TLE
https://i.imgur.com/3mv07SM.png
贏5% 姆咪
def countWinningSequences(self, s: str) -> int:
choice = 'FWE'
mod = 10 ** 9 + 7
@cache
def dp(i, pre, v):
if i==len(s):
return v>0
ans = 0
for cur in choice:
if cur==pre:
pass
elif (s[i]=='F' and cur=='F') or (s[i]=='W' and cur=='W') or
(s[i]=='E' and cur=='E'):
ans += dp(i+1, cur, v)
elif s[i]=='F' and cur =='W':
ans += dp(i+1, cur, v+1)
elif s[i]=='F' and cur =='E':
ans += dp(i+1, cur, v-1)
elif s[i]=='W' and cur =='F':
ans += dp(i+1, cur, v-1)
elif s[i]=='W' and cur =='E':
ans += dp(i+1, cur, v+1)
elif s[i]=='E' and cur =='W':
ans += dp(i+1, cur, v-1)
elif s[i]=='E' and cur =='F':
ans += dp(i+1, cur, v+1)
return ans%mod
return dp(0, '', 0)