今天的
很玄== 我也不知道我怎么解出来的
其实应该不太算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')