Medium

Stone Game II

LAB

Given piles, return the maximum stones Alice can get when players optimally take 1 to 2M piles and update M.

EXAMPLES

Example 1

Input
{
  "piles": [
    2,
    7,
    9,
    4,
    4
  ]
}

Output
10

FUNCTION SHAPE

piles: intArray→int

SOLUTION NOTE

Current player gets suffix_sum - opponent's optimal. Try all valid takes (1 to 2M).

Reveal reference solution +

pythonREFERENCE

def stoneGameII(self, piles: List[int]) -> int:
    n = len(piles)
    suffix_sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + piles[i]

    @cache
    def dp(i, m):
        if i >= n:
            return 0
        if i + 2 * m >= n:
            return suffix_sum[i]

        min_opponent = float('inf')
        for x in range(1, 2 * m + 1):
            min_opponent = min(min_opponent, dp(i + x, max(m, x)))

        return suffix_sum[i] - min_opponent

    return dp(0, 1)

TimeO(n³)

SpaceO(n²)

Open on LeetCode ↗