#877

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Stone Game

Stone Game is a dynamic programming problem where players alternate taking stones from piles to maximize their score.

array math dynamic programming game theory

Problem Statement

In the Stone Game, Alice and Bob take turns removing stones from a row of piles. There is an even number of piles, and each pile contains a positive integer number of stones. Alice always starts first, and each player can choose to take stones either from the start or the end of the row on their turn. The game continues until all piles are taken, and the goal is to end up with the most stones. The total number of stones across all piles is odd, ensuring that there will be no ties in the game.

Given this, you need to determine if Alice can win the game by selecting stones optimally. You are to return true if Alice can win, otherwise false. The problem uses dynamic programming to model the game, taking into account the state transitions for each player's decision at every step.

Examples

Example 1

Input: piles = [5,3,4,5]

Output: true

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

Example details omitted.

Constraints

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

Solution Approach

State Transition Dynamic Programming

The solution involves using dynamic programming to keep track of the current state of the game as the players pick stones from the rows. By calculating the optimal choices for both players in each possible scenario, we can determine if Alice has a winning strategy. The state is represented by subarrays of the pile and transitions are made by selecting stones from the left or right.

Optimal Substructure

The problem exhibits an optimal substructure property, where the solution to a subproblem can be derived from the solution to smaller subproblems. By evaluating the result of selecting stones from either end, we can recursively build the solution to the entire problem. The key insight is that each player aims to maximize their own score while minimizing their opponent's score.

Memoization and Space Optimization

To efficiently solve the problem, memoization can be applied to store intermediate results and avoid redundant calculations. Additionally, space optimization techniques can reduce the space complexity to O(1) by reusing a single array to store only the necessary state transitions.

Complexity Analysis

Metric	Value
Time	O(N^2)
Space	O(1)

The time complexity is O(N^2) due to the nested loops required to evaluate each subarray of piles. Since the problem involves examining all possible pairings of piles, the number of iterations grows quadratically with the number of piles. Space complexity is optimized to O(1) by using a rolling array to store intermediate results, avoiding the need for additional memory allocation for each subarray.

What Interviewers Usually Probe

Look for understanding of dynamic programming with state transitions.
Check if the candidate can explain how optimal substructure applies to the problem.
Evaluate the candidate’s ability to optimize both time and space complexity.

Common Pitfalls or Variants

Common pitfalls

Not recognizing the optimal substructure and solving the problem by brute force.
Incorrectly calculating the value for subarrays due to not considering both player's moves.
Overcomplicating the space complexity by using unnecessary data structures.

Follow-up variants

Consider variations where players may have different strategies or time constraints.
Test variations with different sizes of input to evaluate how well the solution scales.
Explore how the problem behaves if the total number of stones is even, requiring ties to be handled.

FAQ

What is the time complexity of the Stone Game problem?

The time complexity is O(N^2), where N is the number of piles. This is due to the nested loops used to evaluate all subarrays of the piles.

How does dynamic programming help in solving the Stone Game?

Dynamic programming is used to store intermediate results for each subarray of piles. This avoids recalculating results for the same subproblem multiple times and ensures an optimal solution.

Can Alice always win the Stone Game?

No, Alice can only win if she makes the optimal moves. The outcome depends on the configuration of the piles and the choices made by both players.

What is the role of state transitions in the Stone Game?

State transitions are used to model the different scenarios as players take turns. The game’s state depends on the choices made by both players, and these transitions are key to determining if Alice can win.

How can the space complexity of the Stone Game be optimized?

The space complexity can be reduced to O(1) by using a rolling array to store only the necessary state transitions, instead of storing all subarray results.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i, j)$ that represents the maximum difference in the number of stones between the current player and the other player when considering piles from the $i$-th to the $j$-th. The answer is then $dfs(0, n - 1) \gt 0$.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @cache
        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            return max(piles[i] - dfs(i + 1, j), piles[j] - dfs(i, j - 1))

        return dfs(0, len(piles) - 1) > 0

Solution 2: Dynamic Programming

We can also use dynamic programming. Define $f[i][j]$ as the maximum difference in the number of stones the current player can obtain over the other player from piles $piles[i..j]$. The final answer is then $f[0][n - 1] \gt 0$.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @cache
        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            return max(piles[i] - dfs(i + 1, j), piles[j] - dfs(i, j - 1))

        return dfs(0, len(piles) - 1) > 0

Continue Practicing

#1140 stone game ii #486 predict the winner #1406 stone game iii