330. Stone Game II

The state is (i, M): the game faces piles[i:] and the current player may grab 1..2M piles. Maximizing your own stones equals maximizing suffix[i] minus whatever the opponent then guarantees from the smaller state. Fill dp bottom-up over i (right to left) and every M.

State: where we are, and how much reach we have

At any moment the untouched piles are a suffix piles[i:], and the only other thing that matters is M, which caps this turn's grab to 1..2M. So the state is the pair (i, M).

Let dp[i][M] = the maximum stones the player to move can collect from piles[i:], given the current M, when both play optimally.

The recurrence

Let suffix[i] = piles[i] + piles[i+1] + ... + piles[n-1] — all the stones still on the table.

When the current player grabs the first X piles (1 <= X <= 2M), they end up with everything that remains minus what the opponent secures afterward:

stones for me = suffix[i] - dp[i+X][max(M, X)]

because the opponent, moving next from state (i+X, max(M, X)), will optimally take dp[i+X][max(M,X)], and those come out of the shared remaining pool suffix[i]. The current player picks the X that maximizes this:

dp[i][M] = max over X in 1..2M of ( suffix[i] - dp[i+X][max(M, X)] )

Base / shortcut: if i + 2M >= n the player can grab all remaining piles in one move, so dp[i][M] = suffix[i].

Fill i from n-1 down to 0 (so larger indices are ready). The answer is dp[0][1] — Alice starts at index 0 with M = 1.

Worked example

piles = [2, 7, 9, 4, 4], suffix = [26, 24, 17, 8, 4].

The key states (right to left):

• Deep states where i + 2M >= n just return suffix[i] (grab everything).
• dp[0][1]: X = 1 → 26 - dp[1][1]; X = 2 → 26 - dp[2][2]. Working the smaller states out gives dp[1][1] = 16 and dp[2][2] = 17, so dp[0][1] = max(26 - 16, 26 - 17) = max(10, 9) = 10.

Alice's best is 10 (take just the first pile of 2, then respond optimally).

Complexity

• Time: O(n^3) — O(n^2) states, each scanning up to 2M = O(n) choices.
• Space: O(n^2) for the dp[i][M] table.

class Solution {
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[] suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + piles[i];
        }
        // dp[i][m] = max stones the player to move can get from piles[i:] with current M = m.
        int[][] dp = new int[n + 1][n + 2];
        for (int i = n - 1; i >= 0; i--) {
            for (int m = 1; m <= n; m++) {
                if (i + 2 * m >= n) {
                    dp[i][m] = suffix[i];
                } else {
                    int best = 0;
                    for (int x = 1; x <= 2 * m; x++) {
                        best = Math.max(best, suffix[i] - dp[i + x][Math.min(Math.max(m, x), n)]);
                    }
                    dp[i][m] = best;
                }
            }
        }
        return dp[0][1];
    }
}