Stone Game

Stone Game: the approach in brief

The problem

You are given an array of piles in piles, where each value is the number of stones in one pile. The piles remain in their original order, and two players take turns removing exactly one pile from either the left or right end of the remaining array.

Pattern

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

Approach outline

1. Focus on the score difference between the player whose turn it is and the other player, rather than tracking both totals separately.
2. For any remaining contiguous interval, the current player has only two choices: take its leftmost pile or its rightmost pile.
3. After taking one end, the opponent becomes the current player on the smaller interval, so its best score difference should be subtracted.

Complexity

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