{x}
blog image

Stone Game

Alice and Bob play a game with piles of stones. There are an even 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. The total number of stones across all the piles is odd, so there are no ties.

Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.

 

Example 1:

Input: piles = [5,3,4,5]
Output: true
Explanation: 
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.

Example 2:

Input: piles = [3,7,2,3]
Output: true

 

Constraints:

  • 2 <= piles.length <= 500
  • piles.length is even.
  • 1 <= piles[i] <= 500
  • sum(piles[i]) is odd.

Solution Explanation for LeetCode 877: Stone Game

This problem explores the concept of game theory. Alice and Bob take turns picking stones from either end of a pile. The goal is to determine if Alice can win assuming optimal play from both players.

Key Insight: Alice always wins. This isn't immediately obvious, but a clever observation simplifies the problem significantly. Because there's an even number of piles and the total number of stones is odd, Alice can always guarantee a win through a simple strategy.

Solution 1: Top-Down Dynamic Programming (with Memoization)

This approach uses recursion with memoization to explore the game tree.

  • dfs(i, j): This recursive function represents the maximum difference in stones Alice can achieve between her score and Bob's score, starting with piles from index i to j.
  • Base Case: If i > j (no piles left), the difference is 0.
  • Recursive Step: Alice chooses either piles[i] or piles[j]. The optimal choice is the one that maximizes her advantage (her score minus Bob's score). Bob then plays optimally, leading to the recursive call dfs(i + 1, j) or dfs(i, j - 1).
  • Memoization: The @cache decorator (Python) or f[i][j] array (other languages) stores the results of subproblems to avoid redundant calculations.
  • Return Value: The function returns true if dfs(0, n-1) > 0, meaning Alice has a winning strategy.

Time Complexity Analysis (Solution 1): O(N^2), where N is the number of piles. This is because each state (i, j) is visited at most once due to memoization. The number of possible states is roughly N^2.

Space Complexity Analysis (Solution 1): O(N^2) for the memoization table.

Solution 2: Bottom-Up Dynamic Programming

This approach uses iterative dynamic programming to avoid recursion.

  • Initialization: f[i][i] = piles[i] for all i. Each pile initially has its own stone value.
  • Iteration: The outer loop iterates from the second to last pile backward, and the inner loop iterates from the pile after i to the last pile.
  • Transition: f[i][j] = max(piles[i] - f[i + 1][j], piles[j] - f[i][j - 1]). This calculates the maximum difference Alice can achieve from the interval [i, j], considering the choices of picking from either end and Bob's optimal response.
  • Result: f[0][n - 1] represents the maximum difference Alice can achieve. If it's greater than 0, Alice wins.

Time Complexity Analysis (Solution 2): O(N^2). The nested loops iterate through all possible sub-arrays.

Space Complexity Analysis (Solution 2): O(N^2) for the DP table f.

Why Alice Always Wins (Without DP):

A simpler, non-DP solution exists because Alice always wins. She can guarantee a win by focusing on having a larger sum of stones than Bob. She can accomplish this without explicitly computing the optimal strategy. Consider these points:

  • Alice's Strategy: If the sum of piles in even indices is greater than the sum of piles in odd indices, Alice takes piles from even indices. Otherwise, she takes piles from odd indices.
  • Guaranteed Win: Because there's an odd total sum of stones and an even number of piles, the sum of piles in either even or odd indices will be greater than the other.

This simplified understanding shows why the DP solutions (which prove Alice wins in every case) might be overkill for this specific problem. However, the DP solutions are valuable for understanding general game-theory problems and are more flexible if the problem constraints were changed.