Stone Game Ii - Leetcode Solution

Problem Statement: Alex and Lee continue their games with piles of stones. There are a 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.

Alex and Lee take turns, with Alex starting first. Initially, M=1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 ≤ X ≤ 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Input: piles = [2,7,9,4,4] Output: 10 Explanation: Alex chooses [2,7] Then Lee has to choose [9,4,4]. Alex can choose [4,4] Since Lee chooses [9], Alex can get 2 + 7 + 4 + 4 = <<2+7+4+4=17>>17 stones. Lee can get 9. Alex can choose remaining piles [2]. Alex can get 10 stones. Thus the total number of stones Alex can get is 17 + 10 = 27.

Solution: This is a game theory problem where two players play optimally to maximize their own gains. To solve the problem, we can use dynamic programming and the concept of prefix sums.

We first calculate the prefix sum of the piles array. This helps us to calculate the number of stones in any subarray in constant time complexity.

The next step is to use dynamic programming to calculate the maximum number of stones Alex can get. We use a 2D dp array, where dp[i][j] represents the maximum number of stones that Alex can get if the game starts from the ith pile and the maximum number of piles that Alex can pick on his turn is j.

The base case for the dp array is dp[n][j] = 0, where n is the number of piles and j is any value from 1 to 2n.

To calculate the remaining entries in the dp array, we need to iterate through every pile and every possible value of j. We use a variable called M to represent the maximum number of piles that Alex can pick on his turn. Initially, M = 1.

For each pile i, we iterate through every possible value of M from 1 to 2*M. We calculate the maximum number of stones that Alex can get if he picks M piles starting from pile i.

The calculation of the maximum number of stones is done as follows:

• If Alex picks all the remaining piles i...n-1, he gets all the stones in these piles (prefixSum[n-1] - prefixSum[i-1]).
• Otherwise, Alex picks M piles starting from pile i and Lee plays his turn. Lee picks a subset of remaining piles j...n-1 such that the number of piles Lee picks is between 1 and 2*M. If Lee picks piles j...j+k-1, then Alex can get the remaining stones in piles i...j-1 and the maximum number of stones that Alex can get in the remaining game is dp[j][max(M, k)]. Therefore, the total number of stones that Alex can get in this case is prefixSum[j-1] - prefixSum[i-1] + (prefixSum[n-1] - prefixSum[j-1] - dp[j][max(M, k)]).

We take the maximum of these two cases and store it in dp[i][M]. The final answer is dp[0][1].

Python Code:

def stoneGameII(piles: List[int]) -> int: n = len(piles) prefixSum = [0] * n prefixSum[0] = piles[0] for i in range(1, n): prefixSum[i] = prefixSum[i-1] + piles[i]

dp = [[0] * (2*n) for _ in range(n+1)]
for j in range(1, 2*n):
    dp[n][j] = 0

for i in range(n-1, -1, -1):
    M = 1
    for j in range(1, 2*M+1):
        if i + j > n:
            break
        dp[i][M] = max(dp[i][M], prefixSum[n-1] - prefixSum[i-1])
    
    for j in range(M+1, 2*M+1):
        if i + j > n:
            break
        for k in range(1, j):
            dp[i][M] = max(dp[i][M], prefixSum[j-1] - prefixSum[i-1] + (prefixSum[n-1] - prefixSum[j-1] - dp[j][max(M, k)]))
    
    M = max(M, j)

return dp[0][1]

1