Re: [閒聊] 每日leetcode
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1年前 (2024/10/15 23:34)推噓2(2推 0噓 0→)留言2則, 2人參與討論串991/1548 (看更多)
競賽放棄的那一題
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)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729006441.A.3E6.html
推
10/15 23:39,
1年前
, 1F
10/15 23:39, 1F
推
10/16 00:57,
1年前
, 2F
10/16 00:57, 2F
討論串 (同標題文章)
完整討論串 (本文為第 991 之 1548 篇)：