Problem Description

In the Stone Game problem, you are given an array piles of 2n positive integers, where each element represents a pile of stones. Two players, Alice and Bob, take turns. On each turn, a player picks either the first or last pile from the row. Alice always goes first. The goal for each player is to maximize the total number of stones they collect.

The problem asks: Assuming both players play optimally, will Alice always win? Return true if Alice can win, otherwise false.

• There are always an even number of piles.
• Each pile has a positive number of stones.
• Both players cannot pick the same pile twice.
• Both players play optimally to maximize their own score.

Thought Process

At first glance, this problem seems similar to other two-player, turn-based games where you must maximize your score while minimizing your opponent’s. A brute-force solution would consider every possible sequence of picks for both players, but this quickly becomes infeasible as the number of piles increases.

The main challenge is to determine the best move at each step, knowing your opponent will also play optimally. This is a classic minimax problem, where you need to maximize your own gain while minimizing your opponent's.

However, the constraints (even number of piles, all positive, and Alice goes first) hint at possible optimizations. For example, can we use dynamic programming to avoid recalculating the same subproblems? Or is there a mathematical insight that guarantees Alice's win under these rules?

Solution Approach

There are two main approaches for this problem: a dynamic programming (DP) solution and a game theory/observation-based solution.

• Dynamic Programming:
  • Define dp[i][j] as the maximum number of stones the current player can achieve more than their opponent, considering only piles from index i to j.
  • At each turn, the player can pick either piles[i] or piles[j]. After the pick, the opponent will play optimally on the remaining subarray.
  • The recurrence relation is:
    • dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
  • Base case: when i == j, dp[i][j] = piles[i] (only one pile left to take).
  • If dp[0][n-1] > 0, Alice can secure more stones than Bob, so she wins.
• Mathematical Insight:
  • Since the number of piles is even, Alice can always choose either all even or all odd indexed piles.
  • She can compare the total stones in even vs. odd indexed piles and always pick from the more valuable set.
  • This guarantees Alice can always win if she plays optimally.

For completeness, we present the full DP solution, which works for any variant, and is easy to implement.

Example Walkthrough

Let's consider piles = [5, 3, 4, 5].

1. Alice can choose either 5 (left) or 5 (right). Let's say she picks the left 5.
   • Now Bob chooses between 3 and 5. He will pick 5.
   • Alice is left with 3 and 4. She picks 4.
   • Bob gets the remaining 3.
   • Totals: Alice = 5 + 4 = 9, Bob = 5 + 3 = 8. Alice wins.
2. If Alice picked the right 5 first, a similar process ensures she still wins.
3. The DP table will confirm that dp[0][3] = 1 (Alice can win by at least 1 stone).

Time and Space Complexity

• Brute-force: The naive recursive solution explores all possible choices for both players, leading to O(2^n) time complexity (exponential), as each player has two choices per turn.
• Dynamic Programming:
  • There are O(n^2) subproblems (for each i and j).
  • Each subproblem is solved in constant time.
  • Overall time and space complexity: O(n^2).
• Observation-based: If using the mathematical insight, the solution is O(1) time and space, as Alice always wins.

Summary

The Stone Game problem is a classic example of two-player game theory, requiring you to think several moves ahead and anticipate your opponent's optimal play. While brute-force recursion is impractical, dynamic programming allows efficient computation by reusing subproblem results. The mathematical insight that Alice can always win due to the even number of piles and optimal play makes this problem elegant and highlights the power of strategic reasoning in algorithms.

Code Implementation

class Solution:
    def stoneGame(self, piles):
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for size in range(2, n + 1):
            for i in range(n - size + 1):
                j = i + size - 1
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
        return dp[0][n - 1] > 0
      

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i) dp[i][i] = piles[i];
        for (int size = 2; size <= n; ++size) {
            for (int i = 0; i <= n - size; ++i) {
                int j = i + size - 1;
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] > 0;
    }
};
      

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i) dp[i][i] = piles[i];
        for (int size = 2; size <= n; ++size) {
            for (int i = 0; i <= n - size; ++i) {
                int j = i + size - 1;
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] > 0;
    }
}
      

var stoneGame = function(piles) {
    const n = piles.length;
    const dp = Array.from({length: n}, () => Array(n).fill(0));
    for (let i = 0; i < n; ++i) dp[i][i] = piles[i];
    for (let size = 2; size <= n; ++size) {
        for (let i = 0; i <= n - size; ++i) {
            let j = i + size - 1;
            dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1] > 0;
};