1140. Stone Game II

Array Math Dynamic Programming Game Theory

Problem Overview

Alice and Bob take turns on piles from the front.

Intuition

Alice and Bob take turns on piles from the front. On a turn with parameter M you may take X in 1..2M piles, then M becomes max(M, X). Both maximize their own stones. The current player from index i with M wants the maximum of (suffix sum from i minus the opponent optimal from the leftover). Cap useful M at about n/2 because once 2M covers the remaining piles you take everything.

Algorithm

1Build suffix[i] = sum(piles[i..n)).
2Bottom-up: for i = n-1..0 and m = 1..(n+1)/2:
3 If 2*m >= n-i: dp[i][m] = suffix[i].
4 Else: dp[i][m] = max over x=1..2m of (suffix[i] - dp[i+x][min(max(m,x), mMax)]).
5Return dp[0][1] (Alice starts with M = 1).

Example Walkthrough

Input: piles = [2, 7, 9, 4, 4]

1.Alice can open with 1 or 2 piles. Optimal play yields Alice 10.
2.One optimal line: Alice takes 2, Bob takes 2+4 of remaining choices under updated M, Alice finishes with more total than Bob.

Output: 10

Common Pitfalls

•Maximize own score via suffix[i] - opponent, not by maximizing immediate take alone.
•Clamp next M to mMax; values beyond that are equivalent to the take-all base case.
•Fill from the end of the array so later states exist before earlier ones.
•Time is O(n^3) in the usual analysis even with the M cap - n <= 100 keeps it fine.

1140.cs

// Approach: Bottom-up game DP. suffix[i] = sum(piles[i..n)). dp[i][m] = max
// stones the current player gets from piles[i..] with parameter M = m. Take
// X in 1..2m piles; opponent then gets dp[i+X][max(m,X)], so you keep
// suffix[i] - that amount. If 2m covers the rest of the array, take everything.
// Cap m at (n+1)/2: larger M never changes the answer once 2M >= remaining.
// Complexity: O(n^3) time (typical for this DP), O(n^2) space.
public class Solution
{
    public int StoneGameII(int[] piles)
    {
        int n = piles.Length;
        int[] suffix = new int[n];
        suffix[n - 1] = piles[n - 1];
        for (int i = n - 2; i >= 0; --i)
            suffix[i] = suffix[i + 1] + piles[i];

        // mMax is enough: once 2*m >= remaining piles, base case applies.
        int mMax = (n + 1) / 2;
        int[,] dp = new int[n, mMax + 1];

        for (int i = n - 1; i >= 0; --i)
        {
            int remaining = n - i;
            for (int m = 1; m <= mMax; ++m)
            {
                if (2 * m >= remaining)
                {
                    dp[i, m] = suffix[i];
                    continue;
                }

                int best = 0;
                int takeLimit = 2 * m;
                for (int x = 1; x <= takeLimit; ++x)
                {
                    int nextM = Math.Max(m, x);
                    if (nextM > mMax)
                        nextM = mMax;
                    best = Math.Max(best, suffix[i] - dp[i + x, nextM]);
                }
                dp[i, m] = best;
            }
        }

        return dp[0, 1];
    }
}

Was this solution helpful?