#1406

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Stone Game III

Stone Game III is a challenging dynamic programming problem based on game theory and state transition logic.

array math dynamic programming game theory

Problem Statement

In the Stone Game III, Alice and Bob take turns choosing stones from a row of stones represented by an integer array called stoneValue. Alice always starts first, and on each turn, the player can pick 1, 2, or 3 stones from the remaining pile. Each stone has a value, and the score of each player is the sum of the values of the stones they pick.

The goal is to determine who wins the game, given that both players play optimally. Alice tries to maximize her score, while Bob tries to minimize Alice's score. If both players end with the same score, the result is a draw. The task is to return the winner: 'Alice', 'Bob', or 'Tie'.

Examples

Example 1

Input: stoneValue = [1,2,3,7]

Output: "Bob"

Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

Example 2

Input: stoneValue = [1,2,3,-9]

Output: "Alice"

Alice must choose all the three piles at the first move to win and leave Bob with negative score. If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose. If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose. Remember that both play optimally so here Alice will choose the scenario that makes her win.

Example 3

Input: stoneValue = [1,2,3,6]

Output: "Tie"

Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

Constraints

1 <= stoneValue.length <= 5 * 104
-1000 <= stoneValue[i] <= 1000

Solution Approach

State Transition Dynamic Programming

The problem can be approached using dynamic programming (DP) to evaluate the optimal moves for each player. Start from the last stone and work backward, using the current stone values to build the solution. At each step, calculate the best possible score for Alice or Bob, considering taking 1, 2, or 3 stones.

Minmax Game Theory Mapping

Map the game to a minmax strategy, where Alice tries to maximize her score and Bob tries to minimize it. The DP state transitions account for this by determining the best possible outcome for both players at each step, based on the remaining stones and the choices made.

Memoization for Efficiency

To optimize the solution, use memoization to store intermediate results in a DP array. This avoids redundant calculations and significantly reduces the time complexity of the solution, especially when dealing with large arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the implementation of the dynamic programming solution. Since each stone requires constant time to evaluate the three possible moves (1, 2, or 3 stones), the time complexity is O(n). Memoization reduces the number of redundant calculations, ensuring that the solution scales efficiently with the input size. The space complexity is O(n) due to the DP table used for memoization.

What Interviewers Usually Probe

Look for an understanding of dynamic programming and game theory concepts.
Ensure the candidate can map the problem to a minmax game scenario.
Assess the candidate’s ability to optimize a recursive solution using memoization.

Common Pitfalls or Variants

Common pitfalls

Overlooking the optimal move for Bob and Alice, which can lead to incorrect strategies.
Failing to implement memoization properly, leading to inefficient solutions.
Misunderstanding the draw condition, which might lead to wrong outputs when the game ends in a tie.

Follow-up variants

Change the game rules by allowing the player to choose more than 3 stones per turn.
Introduce multiple players (e.g., 3 players) instead of just Alice and Bob.
Alter the game so that one player’s goal is to minimize their own score rather than the opponent's score.

FAQ

What is the key pattern for solving Stone Game III?

The key pattern is state transition dynamic programming, which helps evaluate the optimal moves for Alice and Bob based on the remaining stones.

How does the minmax game theory apply to this problem?

In Stone Game III, Alice tries to maximize her score while Bob attempts to minimize it, which can be represented by a minmax game where each player makes optimal moves.

How can memoization improve the solution?

Memoization stores intermediate results in a DP table, avoiding redundant calculations and improving time efficiency for large input sizes.

What happens if both players have the same score?

If Alice and Bob have the same score at the end of the game, the result is a tie.

How can I optimize the solution for larger inputs?

To optimize the solution for larger inputs, use dynamic programming with memoization to avoid recalculating results for the same game states.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i)$, which represents the maximum score difference that the current player can obtain when playing the game in the range $[i, n)$. If $dfs(0) > 0$, it means that the first player Alice can win; if $dfs(0) < 0$, it means that the second player Bob can win; otherwise, it means that the two players tie.

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            ans, s = -inf, 0
            for j in range(3):
                if i + j >= n:
                    break
                s += stoneValue[i + j]
                ans = max(ans, s - dfs(i + j + 1))
            return ans

        n = len(stoneValue)
        ans = dfs(0)
        if ans == 0:
            return 'Tie'
        return 'Alice' if ans > 0 else 'Bob'

Continue Practicing

#1563 stone game v #1140 stone game ii #1690 stone game vii