Stone Game III

Stone Game III: the approach in brief

The problem

You are given an integer array stoneValue representing a row of stones. Alice plays first, and Bob plays second. On each turn, the current player must take one, two, or three stones from the left end of the remaining row and add the values of those stones to that player's score.

Pattern

Stone Game III is a Dynamic Programming (DP) Patterns problem, in the 1D Array (Fibonacci Style) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Approach outline

1. Analyze the game starting at each position in the array, rather than tracking both players separately.
2. A move contributes the sum of the taken stones, after which the opponent faces the suffix that remains.
3. Define a state as the best score difference the player to move can achieve over the other player from a given index.

Complexity

The reference solution runs in O(n) time and O(n) space.