1140. Stone Game II
## 思路
dp(player, i, m)
如果當前player是Alice 就取max, 是Bob 就取min
## Code
```python
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
ALICE, BOB = 0, 1
n = len(piles)
@cache
def dp(p, i, m):
if i == n:
return 0
res = float('-inf') if p == ALICE else float('inf')
if p == ALICE:
curr = 0
for j in range(min(2*m, n-i)):
curr += piles[i+j]
res = max(res, curr + dp(BOB, i+j+1, max(m, j+1)))
else:
for j in range(min(2*m, n-i)):
res = min(res, dp(ALICE, i+j+1, max(m, j+1)))
return res
return dp(ALICE, 0, 1)
```
補個 用前面大大的解法寫的解
不管player, 就看piles[i:]取1~m個 可以拿到的最大值
dp(i, m) = max(suffix_sum[i] - dp(i+x, max(x,m)))
```
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
n = len(piles)
suffix = [0] * n
suffix[-1] = piles[-1]
for i in range(n-2, -1, -1):
suffix[i] = suffix[i+1] + piles[i]
@cache
def dp(i, m):
if i == n:
return 0
if n - i <= 2 * m:
return suffix[i]
res = 0
for j in range(1, 1 + 2 * m):
res = max(res, suffix[i] - dp(i+j, max(j, m)))
return res
return dp(0, 1)
```