竞赛放弃的那一题
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)