Domain 2MediumMEDIUM

Stone Game II

Alice maximizes her stone count in a zero-sum game where the move limit M increases dynamically; solved via minimax with memoization.

Domain: medium•Updated: 2026-09-09
#dynamic programming#recursion#O(N^3)#memoization

Problem Breakdown

We are given an array of piles piles representing stones. Alice and Bob take turns picking from the left side only. The game state is defined by two variables:

  1. Current Index (index): How many piles have been taken so far (from the start).
  2. Multiplier (m): Determines how many consecutive remaining piles a player can pick (X≤2MX \le 2M), and updates after each move to max⁡(M,X)\max(M, X).

Goal: Calculate the maximum stones Alice can secure assuming both players play optimally (Minimax strategy). Since it is effectively a zero-sum game regarding the remaining total stones between turns, maximizing one’s own score from state (i,m)(i, m) is equivalent to minimizing the opponent’s optimal return from that same remaining subgame.

Inputs:

  • piles: List of positive integers (1≤N≤1001 \le N \le 100, values up to 10410^4).
  • Initial State: Alice starts at index 0 with multiplier M=1M=1.

Outputs:

  • An integer representing the maximum stones Alice can get.

Intuition

A brute-force simulation of all possible moves is infeasible due to exponential branching (O(3N)O(3^N) or worse). However, this problem exhibits optimal substructure and overlapping subproblems:

  1. Zero-Sum Property: The total number of remaining stones from any point index onwards (suffix_sum[index]) must be split between the current player and their opponent in future turns. If we know how many stones the opponent can optimally get starting at (index + X, max(M, X)), then our optimal score is simply: My Score=(Total Remaining Stones)−(Opponent’s Optimal Score)\text{My Score} = (\text{Total Remaining Stones}) - (\text{Opponent's Optimal Score})
  2. State Memoization: The game state depends only on the current index and the multiplier MM. Since NN is small (100), we can memoize results for states (index, m) to avoid recomputing them.

Approach

  1. Preprocessing Suffix Sums: Compute an array suffix_sum where suffix_sum[i] holds the sum of all piles from index ii to the end. This allows calculating total available stones in any state in O(1)O(1) time.
  2. Recursive Function with Memoization (dfs(index, m)):
    • Define a function that returns the maximum stones the current player can get starting at index with multiplier m.
    • Iterate through all valid moves XX (from 1 to min⁡(remaining_piles,2⋅M)\min(remaining\_piles, 2 \cdot M)).
    • For each move, recursively call dfs(index + X, max(M, X)) to get the opponent’s best score.
    • Calculate current player’s potential score as suffix_sum[index] - opponent_score.
    • Return the maximum of these scores across all valid XX.
  3. Execution: Call dfs(0, 1) since Alice starts at index 0 with initial multiplier 1.

Complexity Analysis

  • Time Complexity: O(N3)O(N^3).
    • There are approximately NN possible indices and up to NN distinct values of MM reachable (bounded by array length). For each state (i, m), the loop iterates at most 2m≤2n2m \le 2n times. Summing over all states yields a cubic bound relative to N in the worst case analysis for this specific game structure. Given constraints (N=100N=100), operations are roughly ≈106\approx 10^6, which is well within limits (typically 10810^8 ops/sec).
  • Space Complexity: O(N2)O(N^2).
    • We store memoization results for each unique (index, m) pair. The recursion stack depth adds negligible overhead (O(N)O(N)), but the DP table dominates space usage here.

Solution

from functools import lru_cache

def stoneGameII(piles):
    n = len(piles)
    
    # Precompute suffix sums for O(1) total remaining stones calculation
    # suffix_sum[i] represents sum of piles from index i to end
    suffix_sum = [0] * (n + 1)
    current_suffix = 0
    
    # Build suffix array backwards
    for i in range(n - 1, -1, -1):
        current_suffix += piles[i]
        suffix_sum[i] = current_suffix
        
    @lru_cache(None)
    def dfs(index, m):
        # Base case: no more piles left to take
        if index >= n:
            return 0
            
        max_stones_alice_can_get = -1  # Initialize with a value lower than any possible score (stones are positive)
        
        # Alice can choose X from 1 to min(2*M, remaining_piles_count)
        limit = min(n - index, m * 2)
        
        for x in range(1, limit + 1):
            # If we take 'x' piles:
            # Remaining stones available is suffix_sum[index] (total from current point onwards)
            # Opponent will play optimally starting at index + x with new M = max(m, x)
            opponent_score = dfs(index + x, max(m, x))
            
            # My score for this move = Total remaining - What opponent gets
            my_score = suffix_sum[index] - opponent_score
            
            if my_score > max_stones_alice_can_get:
                max_stones_alice_can_get = my_score
                
        return max_stones_alice_can_get

    return dfs(0, 1)

Edge Cases Handled

  • Single Pile: The loop range(1, limit + 1) handles this correctly. If N=1N=1, Alice takes the only pile (X=1X=1), opponent gets 0 (base case returns 0 immediately after index increment or via logic flow if handled carefully). In code: dfs calls with index+1. If index+1 >= n, it returns 0. So score = Total - 0 = Total. Correct.
  • Large Values: Python integers automatically handle arbitrary precision; no overflow issues for sums up to 104×10010^4 \times 100.
  • Empty Input: Constraints specify piles.length >= 1, so we do not need explicit handling for empty lists (though the code would return 0 naturally if logic allowed).
  • Initialization of Max Score: Changed initialization from 0 to -1. Since piles are positive integers, any valid move yields a score ≥1\ge 1. Initializing with -1 ensures that even if multiple moves exist, we correctly pick the maximum. (Note: With N≥1N \ge 1, loop always runs at least once because m≥1m \ge 1 and remaining piles ≥1\ge 1, so max_stones_alice_can_get will be updated).