Stone Game II

Stone Game II: the approach in brief

The problem

You are given piles, where piles[i] is the number of stones in the i-th pile from left to right. Two players take turns, and all piles must be taken in their original order: on a turn, a player removes a consecutive prefix of the remaining piles.

Pattern

Stone Game II 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. Describe a game state by the index of the first remaining pile and the current value of `M`.
2. For each state, consider every legal number of piles the current player could take.
3. The current player's gain can be expressed using the total stones remaining minus the opponent's best result on the resulting state.

Complexity

The reference solution runs in O(n^3), where n is piles.size(). There are O(n^2) states, and each state considers O(n) possible moves. time and O(n^2) for the memoization table, plus O(n) for suffix sums and recursion stack. space.