Skip to main content

1140. Stone Game II

medium

Alice and Bob take stones from the front of an array; each turn lets you take between 1 and 2M piles where M is a growing parameter. State is (start, M), so this is a clean 2D DP.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones. Alice and Bob take turns, with Alice starting first. Initially, M = 1. On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X). The game continues until all the stones have been taken. Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Constraints

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10^4

Examples

Example 1

Input
piles = [2,7,9,4,4]
Output
10

Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Example 2

Input
piles = [1,2,3,4,5,100]
Output
104

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

State: (i, M) where i is the next pile index and M is the current cap parameter. Action: choose x in [1, 2M], take piles[i..i+x-1], opponent plays from (i+x, max(M, x)).

Hint 2

dp[i][M] = maximum stones the current player can collect from suffix piles[i..] given parameter M.

Hint 3

Use suffix sums to compute the remaining total in O(1). The current player's score = totalRemaining - opponentScore.

Hint 4

dp[i][M] = max over x in [1, 2M] of (suffixSum[i] - dp[i+x][max(M, x)]).

Solution approach

Reveal approach

Top-down memoization on (i, M). Precompute suffix sums so totalRemaining(i) is O(1). Base case: if i >= n, return 0. If i + 2*M >= n the current player can take everything remaining, so return suffixSum[i]. Recurrence: dp[i][M] = max over x in [1, 2M] of suffixSum[i] - dp[i+x][max(M, x)] — the current player gets the suffix minus whatever the opponent claims from the position after this move. Answer is dp[0][1]. Cap M by n / 2 + 1 since once 2M >= n - i the recursion bottoms out. Bottom-up sweeps i from n down to 0.

Complexity

Time
O(n^3)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • game-theory
  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →