Stone Game II

How it works

Combining the bottom-up approach with the suffix sum optimization gives us a cleaner solution. Since we treat both players symmetrically (each maximizes their own score), we only need a 2D DP table. The suffix sum lets us compute how many stones the current player gets by subtracting the opponent's optimal result from the remaining total.

Steps

1. Precompute suffix sums where suffix_sum[i] is the total stones from index i to the end.
2. Create a 2D DP array dp[n+1][n+1] initialized to 0.
3. Iterate from i = n-1 down to 0, and for each M from 1 to n.
4. For each X from 1 to 2M (while i + X <= n), compute dp[i][M] = max(dp[i][M], suffix_sum[i] - dp[i+X][max(M, X)]).
5. Return dp[0][1] as Alice's maximum score.

Complexity

• Time complexity: O(n ^ 3)
• Space complexity: O(n ^ 2)

Things to watch for

Misunderstanding the M Parameter Update

A frequent error is updating M incorrectly after a move. The rule is M = max(M, X) where X is the number of piles taken, not M = X or M = M + X. Failing to take the maximum means M might decrease, which violates the game rules and leads to wrong answers.

Confusing Whose Score to Track

Since both players play optimally but only Alice's score matters for the answer, it is easy to mix up the logic. When using the minimax approach, Alice maximizes her score while Bob minimizes it. When using the suffix sum trick, both players maximize their own score, and the recursion naturally handles the alternation.

Off-by-One Errors in Loop Bounds

The player can take X piles where 1 <= X <= 2*M. A common mistake is iterating X from 0 to 2*M or from 1 to 2*M - 1. Ensure your loop correctly covers exactly the valid range of moves, and check that i + X does not exceed the array length before accessing elements.

from typing import List

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] = piles[i] + suffix_sum[i + 1]

        dp = [[0] * (n + 1) for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for M in range(1, n + 1):
                for X in range(1, 2 * M + 1):
                    if i + X > n:
                        break
                    dp[i][M] = max(dp[i][M], suffix_sum[i] - dp[i + X][max(M, X)])

        return dp[0][1]

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();

        vector<int> suffixSum(n, 0);
        suffixSum[n - 1] = piles[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixSum[i] = piles[i] + suffixSum[i + 1];
        }

        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

        for (int i = n - 1; i >= 0; i--) {
            for (int M = 1; M <= n; M++) {
                for (int X = 1; X <= 2 * M; X++) {
                    if (i + X > n) break;
                    dp[i][M] = max(dp[i][M], suffixSum[i] - dp[i + X][max(M, X)]);
                }
            }
        }

        return dp[0][1];
    }
};