1140. Stone Game II

Array
Dynamic Programming
Prefix Sum
Game Theory
Memoization

TIME

O(n^3)

SPACE

O(n^2)

Intuition

Piles are always taken from the front, so the remaining game is fully described by two things: the current index i and the current M. Rather than tracking both players' totals, note that whatever the current player does not take from the suffix, the opponent (playing optimally on the rest) will secure. So:

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

where suffix(i) is the sum of all piles from i onward. The suffix(i) - ... framing converts "how much do I get" into a single value per state.

Approach

Build suffix sums so suffix(i) is O(1).
Memoize dp(i, M):
- If i >= n, return 0 (nothing left).
- If 2M >= n - i, the current player can take everything → return suffix(i).
- Otherwise take the max over X = 1..2M of suffix(i) - dp(i + X, max(M, X)).
Answer is dp(0, 1).

M never needs to exceed n (taking more piles than remain is capped), so the state space is O(n^2) and each state does O(n) work.

Complexity

Time: O(n^3), O(n^2) states, O(n) transitions (about 10^6 at n = 100)
Space: O(n^2), the memo table

Edge Cases

Single pile → Alice takes it → answer is that pile
2M covering the rest → current player takes everything (the early-exit branch)
Greedy "take the most stones now" is wrong (Example 1: taking 2 piles first loses)
Total stones ≤ 100 * 10^4 = 10^6, comfortably within int

Code

from typing import List
from functools import lru_cache


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        """
        1140. Stone Game II
        Time: O(n^3)
        Space: O(n^2)
        """
        n = len(piles)

        # suffix[i] = sum of piles[i:]
        suffix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] + piles[i]

        @lru_cache(maxsize=None)
        def dp(i: int, M: int) -> int:
            # max stones the current player can take from piles[i:]
            if i >= n:
                return 0
            if 2 * M >= n - i:
                return suffix[i]  # can take everything that remains
            best = 0
            for x in range(1, 2 * M + 1):
                # opponent then plays optimally on the rest
                best = max(best, suffix[i] - dp(i + x, max(M, x)))
            return best

        result = dp(0, 1)
        dp.cache_clear()
        return result

/**
 * 1140. Stone Game II
 * Time: O(n^3)
 * Space: O(n^2)
 */
class Solution {
    private int n;
    private int[] suffix;
    private int[][] memo;

    public int stoneGameII(int[] piles) {
        n = piles.length;

        // suffix[i] = sum of piles[i:]
        suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + piles[i];
        }

        memo = new int[n][n + 1];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return dp(0, 1);
    }

    /** Max stones the current player can take from piles[i:]. */
    private int dp(int i, int M) {
        if (i >= n) {
            return 0;
        }
        if (2 * M >= n - i) {
            return suffix[i]; // can take everything that remains
        }
        if (memo[i][M] != -1) {
            return memo[i][M];
        }
        int best = 0;
        for (int x = 1; x <= 2 * M; x++) {
            // opponent then plays optimally on the rest
            best = Math.max(best, suffix[i] - dp(i + x, Math.max(M, x)));
        }
        memo[i][M] = best;
        return best;
    }
}