#1140

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Stone Game II

Stone Game II is a dynamic programming problem where Alice and Bob alternate taking stones from piles to maximize their total.

array math dynamic programming prefix sum game theory

Problem Statement

Alice and Bob are playing a game with piles of stones. The piles are arranged in a row, and each pile contains a positive integer number of stones. On their turn, a player can take all the stones from the first X piles, where 1 <= X <= 2M. The objective is for each player to maximize the total number of stones they collect. The number of piles and the number of stones in each pile are provided.

The game starts with Alice, and both players take turns. Initially, M = 1, and after each turn, the value of M is updated to the maximum number of piles taken. The goal is to determine the maximum number of stones Alice can collect, given optimal play from both players.

Examples

Example 1

Input: piles = [2,7,9,4,4]

Output: 10

So we return 10 since it's larger.

Example 2

Input: piles = [1,2,3,4,5,100]

Output: 104

Example details omitted.

Constraints

1 <= piles.length <= 100
1 <= piles[i] <= 104

Solution Approach

State Transition Dynamic Programming

Use dynamic programming to track the best possible outcome for each state. Define a state as (i, m), where 'i' is the index of the current pile, and 'm' is the maximum number of piles the current player can take. The DP solution uses recursion to calculate the optimal choice at each stage while considering the next player's turn.

Recursive Function with Memoization

The recursive function calculates the maximum number of stones that can be collected starting from a given pile. Memoization ensures that previously computed results are reused, making the solution efficient even for larger inputs. Each state transition considers all valid choices (1 to 2M piles) for the current player.

Handling Turn-based Play

The turn-based nature of the game requires that the recursive function account for alternating players. At each step, the function updates the current state based on the number of piles taken and adjusts M accordingly. The challenge lies in making the right choices while predicting the opponent’s optimal responses.

Complexity Analysis

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

The time and space complexity depend on the number of states explored by the dynamic programming solution. With memoization, the number of states is O(n * M), where n is the number of piles and M is the maximum number of piles a player can take. The time complexity of the solution is O(n * M) due to the recursive nature of the approach and the memoization table lookup.

What Interviewers Usually Probe

Assess the candidate’s understanding of dynamic programming and its application to game theory problems.
Look for the ability to design a solution with efficient memoization to handle multiple states.
Evaluate how well the candidate balances between recursion and optimization techniques for state transitions.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly implement the state transition, which can result in incorrect results or inefficient solutions.
Overlooking the fact that the state space grows based on both the pile index and the maximum piles a player can take.
Not optimizing the solution with memoization, leading to excessive recomputation and poor performance on larger inputs.

Follow-up variants

Consider modifying the game rules to allow players to take up to X piles, where X is a fixed number rather than based on M.
Change the problem to allow players to skip turns, requiring a more complex state transition.
Implement a variant where players can take stones from anywhere in the array rather than only starting from the first pile.

FAQ

What is the optimal strategy for Alice in the Stone Game II?

The optimal strategy involves using dynamic programming to track the maximum stones Alice can collect, considering the number of piles available at each step and the opponent’s responses.

How do I use dynamic programming to solve Stone Game II?

State transitions are tracked using dynamic programming, where each state is defined by the current pile index and the maximum number of piles that can be taken. This allows for efficient calculation of the best moves.

What does the state transition dynamic programming pattern mean for Stone Game II?

State transition dynamic programming means solving the problem by recursively determining the best choice at each state and transitioning between states based on the current conditions of the game.

Why is memoization crucial in Stone Game II?

Memoization is crucial because it ensures that previously computed results are reused, making the solution efficient by avoiding redundant calculations, especially for larger inputs.

Can I use a greedy approach to solve Stone Game II?

A greedy approach would not work because it doesn't account for future optimal decisions by the opponent. Dynamic programming is needed to optimize the overall game outcome considering both players' choices.

terminal

Solution

Solution 1: Prefix Sum + Memoization Search

Since the player can take all the stones from the first $X$ piles each time, that is, they can take the stones from an interval, we can first preprocess a prefix sum array $s$ of length $n+1$, where $s[i]$ represents the sum of the first $i$ elements of the array `piles`.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @cache
        def dfs(i, m):
            if m * 2 >= n - i:
                return s[n] - s[i]
            return max(
                s[n] - s[i] - dfs(i + x, max(m, x)) for x in range(1, m << 1 | 1)
            )

        n = len(piles)
        s = list(accumulate(piles, initial=0))
        return dfs(0, 1)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @cache
        def dfs(i, m):
            if m * 2 >= n - i:
                return s[n] - s[i]
            return max(
                s[n] - s[i] - dfs(i + x, max(m, x)) for x in range(1, m << 1 | 1)
            )

        n = len(piles)
        s = list(accumulate(piles, initial=0))
        return dfs(0, 1)

Continue Practicing

#1728 cat and mouse ii #486 predict the winner #1248 count number of nice subarrays