今天的 很玄== 我也不知道我怎麼解出來的 其實應該不太算dp 好像比較算BFS 先看hint def dp(i,M,player) -> 回傳 只看piles[i:]、當回合是player(AorB)、且M=M的情況下 A能得到的最多pillar數 若player=='A' 就窮舉A能拿的pile選擇，然後取最大ans回傳 若player=='B' 也要窮舉，這時也要以B能拿到最多pile為考量(因為optimal) 然後回傳這時'A'拿到的pile數 其實就等於sum(piles[i:])-maximum_B_can_take 大概是這樣 然後記得記一下碰過的地方 沒記會TLE 雖然記了能過 但還是很爛 不過我不太想深究了 這題情境設定有說不出的怪== def stoneGameII(self, piles: List[int]) -> int: traveled = {} def dp(i, M, player): if i>=len(piles): return 0 if (i,M,player) in traveled.keys(): return traveled[(i,M,player)] if player == 'A': ans = 0 for j in range(1, 2*M+1): if i+j <= len(piles): ans = max(sum(piles[i:i+j])+dp(i+j, max(M,j), 'B'), ans) traveled[(i,M,player)] = ans return ans else: ans = 0 for j in range(1, 2*M+1): ans = max(sum(piles[i:])-dp(i+j, max(M,j), 'A'),ans) traveled[(i,M,player)] = sum(piles[i:])-ans return traveled[(i,M,player)] return dp(0,1,'A') -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724167048.A.215.html ※ 編輯: DJYOMIYAHINA (125.229.37.69 臺灣), 08/20/2024 23:22:19