Stone Game II

Problem Description

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 ≤ X ≤ 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Examples

Constraints

• 1 ≤ piles.length ≤ 100
• 1 ≤ piles[i] ≤ 10⁴

MiniMax DP with Suffix Sums

Let suffixSum[i] be the sum of all piles from index i to the end of the array. We define a recursive helper function helper(i, M): the maximum stones the current player can obtain starting from index i with parameter M.

From index i, the player can choose to take any number of piles X from 1 to 2M:

• If they take X piles, they get suffixSum[i] - helper(i + X, max(M, X)) (since the total stones left from i is suffixSum[i], and the opponent will play optimally to get helper(i + X, max(M, X)) stones from the remaining piles).
• We want to maximize this value over all possible choices of X.

The base case: if i + 2M >= n, the player can simply take all remaining piles: return suffixSum[i].

We memoize the results using a 2D cache or DP table indexed by [index][M].

Solution: Memoized Minimax DP

import java.util.*;

class Solution {
    private int[] suffixSum;
    private int[][] memo;
    private int n;

    public int stoneGameII(int[] piles) {
        n = piles.length;
        suffixSum = new int[n];
        suffixSum[n - 1] = piles[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }

        // M can grow up to n, so memo table size is n x (n + 1)
        memo = new int[n][n + 1];

        return dfs(0, 1);
    }

    private int dfs(int i, int M) {
        if (i == n) return 0;
        if (i + 2 * M >= n) return suffixSum[i]; // take all remaining
        if (memo[i][M] > 0) return memo[i][M];

        int maxStones = 0;
        for (int X = 1; X <= 2 * M; X++) {
            int opponentStones = dfs(i + X, Math.max(M, X));
            maxStones = Math.max(maxStones, suffixSum[i] - opponentStones);
        }

        memo[i][M] = maxStones;
        return maxStones;
    }
}

class Solution:
    def stoneGameII(self, piles: list[int]) -> int:
        n = len(piles)
        suffix_sum = [0] * n
        suffix_sum[-1] = piles[-1]
        for i in range(n - 2, -1, -1):
            suffix_sum[i] = suffix_sum[i + 1] + piles[i]

        memo = {}

        def dfs(i: int, M: int) -> int:
            if i == n:
                return 0
            if i + 2 * M >= n:
                return suffix_sum[i]
            if (i, M) in memo:
                return memo[(i, M)]

            max_stones = 0
            for X in range(1, 2 * M + 1):
                opponent_stones = dfs(i + X, max(M, X))
                max_stones = max(max_stones, suffix_sum[i] - opponent_stones)

            memo[(i, M)] = max_stones
            return max_stones

        return dfs(0, 1)

#include <vector>
#include <numeric>
#include <algorithm>

class Solution {
    std::vector<int> suffixSum;
    std::vector<std::vector<int>> memo;
    int n;

    int dfs(int i, int M) {
        if (i == n) return 0;
        if (i + 2 * M >= n) return suffixSum[i];
        if (memo[i][M] > 0) return memo[i][M];

        int maxStones = 0;
        for (int X = 1; X <= 2 * M; X++) {
            int opponentStones = dfs(i + X, std::max(M, X));
            maxStones = std::max(maxStones, suffixSum[i] - opponentStones);
        }

        return memo[i][M] = maxStones;
    }

public:
    int stoneGameII(std::vector<int>& piles) {
        n = piles.size();
        suffixSum.resize(n);
        suffixSum[n - 1] = piles[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }

        memo.assign(n, std::vector<int>(n + 1, 0));
        return dfs(0, 1);
    }
};

Complexity Analysis:

• Time Complexity: O(N³) where N is the length of piles. There are N * N states in the memo table, and for each state, the transition loop runs up to 2M times (which is bounded by N).
• Space Complexity: O(N²) to store the memoization table.

← All Problems