今天的
很玄== 我也不知道我怎麼解出來的
其實應該不太算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')