競賽放棄的那一題 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