1140. Stone Game II

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.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

Example 2:

Input: piles = [1,2,3,4,5,100]
Output: 104

Constraints:

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

Approach 01:

#include <algorithm>
#include <vector>

class Solution {
public:
    int stoneGameII(std::vector<int>& piles) {
        const int numberOfPiles = piles.size();
        std::vector<std::vector<int>> memo(numberOfPiles, std::vector<int>(numberOfPiles));
        
        // Compute the suffix sum for each index, which represents the sum of all elements from that index to the end.
        std::vector<int> suffixSum = piles; // suffixSum[i] := sum(piles[i..n))
        for (int i = numberOfPiles - 2; i >= 0; --i) {
            suffixSum[i] += suffixSum[i + 1];
        }

        // Start the recursion to find the maximum stones Alice can collect
        return getMaxStones(suffixSum, 0, 1, memo);
    }

private:
    // This function recursively determines the maximum number of stones Alice can collect
    // starting from the current index with the given value of M.
    int getMaxStones(const std::vector<int>& suffixSum, int currentIndex,
                     int maxM, std::vector<std::vector<int>>& memo) {
        // If the current player can take all remaining piles, return the sum of those piles
        if (currentIndex + 2 * maxM >= memo.size()) {
            return suffixSum[currentIndex];
        }

        // If this state has already been computed, return the stored result to avoid recomputation
        if (memo[currentIndex][maxM] > 0) {
            return memo[currentIndex][maxM];
        }

        // Calculate the minimum number of stones the opponent can leave to Alice
        int minimumOpponentStones = suffixSum[currentIndex];

        // Iterate over all possible choices for X, where X ranges from 1 to 2 * M
        // and determine the best worst-case scenario
        for (int X = 1; X <= 2 * maxM; ++X) {
            minimumOpponentStones = std::min(minimumOpponentStones, getMaxStones(suffixSum, currentIndex + X, std::max(maxM, X), memo));
        }

        // Store the result in memo and return the maximum stones Alice can collect from this point
        return memo[currentIndex][maxM] = suffixSum[currentIndex] - minimumOpponentStones;
    }
};

class Solution:
    def stoneGameII(self, piles):
        numberOfPiles = len(piles)
        memo = [[0] * numberOfPiles for _ in range(numberOfPiles)]
        
        # Compute the suffix sum for each index, which represents the sum of all elements from that index to the end.
        suffixSum = piles[:]  # suffixSum[i] := sum(piles[i..n))
        for i in range(numberOfPiles - 2, -1, -1):
            suffixSum[i] += suffixSum[i + 1]

        # Start the recursion to find the maximum stones Alice can collect
        return self.getMaxStones(suffixSum, 0, 1, memo)

    def getMaxStones(self, suffixSum, currentIndex, maxM, memo):
        # If the current player can take all remaining piles, return the sum of those piles
        if currentIndex + 2 * maxM >= len(memo):
            return suffixSum[currentIndex]

        # If this state has already been computed, return the stored result to avoid recomputation
        if memo[currentIndex][maxM] > 0:
            return memo[currentIndex][maxM]

        # Calculate the minimum number of stones the opponent can leave to Alice
        minimumOpponentStones = suffixSum[currentIndex]

        # Iterate over all possible choices for X, where X ranges from 1 to 2 * M
        # and determine the best worst-case scenario
        for X in range(1, 2 * maxM + 1):
            minimumOpponentStones = min(minimumOpponentStones, self.getMaxStones(suffixSum, currentIndex + X, max(maxM, X), memo))

        # Store the result in memo and return the maximum stones Alice can collect from this point
        memo[currentIndex][maxM] = suffixSum[currentIndex] - minimumOpponentStones
        return memo[currentIndex][maxM]

Time Complexity

• Suffix Sum Computation:

  Computing the suffix sum array involves iterating through the piles array once, which takes \( O(n) \) time, where \( n \) is the number of piles.

• Recursive Function with Memoization:

  The recursive function getMaxStones is called for each state defined by a pair (currentIndex, maxM). The number of possible states is \( O(n^2) \), where \( n \) is the number of piles, as currentIndex ranges from 0 to \( n-1 \) and `maxM` ranges from 1 to \( n \). For each state, the function iterates up to \( 2 \cdot \text{maxM} \), which in the worst case is \( O(n) \). Therefore, the time complexity of the recursion with memoization is \( O(n^3) \).

• Overall Time Complexity:

  The overall time complexity is \( O(n^3) \), combining the suffix sum computation and the recursive function with memoization.

Space Complexity

• Memoization Table:

  The memoization table memo has dimensions \( n \times n \), requiring \( O(n^2) \) space.

• Suffix Sum Array:

  The suffix sum array requires \( O(n) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n^2) \), dominated by the memoization table.