877. Stone Game

Array Math Dynamic Programming Game Theory

Problem Overview

Alice and Bob take turns removing a pile from either end; both play optimally and Alice starts.

Intuition

Alice and Bob take turns removing a pile from either end; both play optimally and Alice starts. The winner is who ends with more stones. Store the optimal score gap (current player minus opponent) on every subarray of piles. Taking an end adds that pile and subtracts the opponent gap on what remains, so Alice wins when the full-array gap is positive.

Algorithm

1Clone piles into dp; length-1 intervals just hold the single pile value.
2For distance d = 1..n-1, for each right j with i = j - d:
3 dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1]).
4Return true iff dp[n - 1] > 0.

Example Walkthrough

Input: piles = [5, 3, 4, 5]

1.Alice can open on either 5. Optimal play yields Alice 10 and Bob 8.
2.Full-array gap dp[n-1] ends positive, so Alice wins.

Output: true

Common Pitfalls

•Strict inequality: Stone Game requires Alice strictly ahead (ties are not wins).
•Constraints guarantee even n and positive piles, so Alice can always force a win; DP still proves it generally.
•Fill by increasing interval length so shorter segments are ready before longer ones.
•In-place 1D DP must walk j right-to-left for each d so values are not overwritten early.

877.cs

// Approach: Same minimax interval DP as Predict the Winner. dp[j] for interval
// [i, j] is the best score gap (current picker minus opponent) under optimal play.
// Expand by length; each end pick yields pile value minus the opponent's gap on the
// leftover segment. Alice wins on the full array when the gap is strictly positive.
// Complexity: O(n^2) time and O(n) space.
public class Solution
{
    public bool StoneGame(int[] piles)
    {
        int n = piles.Length;
        int[] dp = (int[])piles.Clone();

        for (int d = 1; d < n; ++d)
            for (int j = n - 1; j - d >= 0; --j)
            {
                int i = j - d;
                dp[j] = Math.Max(piles[i] - dp[j], piles[j] - dp[j - 1]);
            }

        return dp[n - 1] > 0;
    }
}

Was this solution helpful?