Stone Game III

How it works

Since each state only depends on the next three states (dp[i+1], dp[i+2], dp[i+3]), we can reduce space from O(n) to O(1) by using a rolling array of size 4. We use modulo arithmetic to cycle through the array indices as we process positions from right to left.

Steps

1. Create a small DP array dp[4] initialized to 0.
2. Iterate from i = n-1 down to 0.
3. For each i, set dp[i % 4] = negative infinity. Try taking 1, 2, or 3 stones, accumulating the total and computing dp[i % 4] = max(dp[i % 4], total - dp[(j + 1) % 4]).
4. The value dp[0] represents Alice's advantage. Return "Alice" if positive, "Bob" if negative, "Tie" if zero.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Not Handling Negative Stone Values

Unlike other stone game problems, this one allows negative values. Greedily taking the maximum stones does not work because sometimes it is better to take fewer stones to force the opponent into a bad position. Your DP must consider all choices (1, 2, or 3 stones) even when some have negative values.

Returning the Wrong Output Type

The problem asks for a string ("Alice", "Bob", or "Tie"), not a boolean or numeric score. A common mistake is returning the score difference instead of comparing it to determine the winner. Always convert the final score comparison into the correct string result.

Incorrect Base Case Handling

When the index reaches or exceeds the array length, the remaining score is zero. Initializing this incorrectly or not handling the edge case where fewer than 3 stones remain causes out-of-bounds errors or wrong results. Ensure your loop condition properly checks i + X <= n before accessing elements.

Forgetting Both Players Play Optimally

Assuming Bob plays suboptimally (e.g., always takes 1 stone) leads to incorrect results. The DP must model Bob as a rational player who also maximizes his own score. In the score-difference formulation, this is handled by subtracting the opponent's optimal result from the current player's gain.

from typing import List

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [0] * 4

        for i in range(n - 1, -1, -1):
            total = 0
            dp[i % 4] = float("-inf")
            for j in range(i, min(i + 3, n)):
                total += stoneValue[j]
                dp[i % 4] = max(dp[i % 4], total - dp[(j + 1) % 4])

        if dp[0] == 0:
            return "Tie"
        return "Alice" if dp[0] > 0 else "Bob"

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int n = stoneValue.size();
        vector<int> dp(4, 0);

        for (int i = n - 1; i >= 0; --i) {
            int total = 0;
            dp[i % 4] = INT_MIN;
            for (int j = i; j < min(i + 3, n); ++j) {
                total += stoneValue[j];
                dp[i % 4] = max(dp[i % 4], total - dp[(j + 1) % 4]);
            }
        }

        if (dp[0] == 0) return "Tie";
        return dp[0] > 0 ? "Alice" : "Bob";
    }
};