Stone Game - Leetcode Solution

Problem statement:

Alex and Lee 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 is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or 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 Alex and Lee play optimally, return True if Alex wins the game, or False if Lee wins.

Example 1:

Input: piles = [5,3,4,5] Output: true Explanation: Alex starts first, and can only take the first 5 or the last 5. Say he takes the first 5, so that the row becomes [3, 4, 5]. If Lee takes 4, we get [3, 5] and Alex takes 5 to win with 10 vs 4. If Lee takes 5, we get [3, 4] and Alex takes 4 to win with 9 vs 5. This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

Solution:

The problem requires us to return whether Alex wins the game if both players play optimally. There are two key observations to make:

1. There is no tie in the game as the number of stones is odd.
2. When Alex takes a pile of stones, Lee can either take the next pile or the last pile. Since they play optimally, Lee will take the pile that minimizes the number of stones Alex can take in his next turn.

Based on these observations, we can solve the problem using dynamic programming. We will define dp[i][j] as the maximum number of stones that Alex can win from piles i to j. The base cases are dp[i][i] = piles[i] and dp[i][i+1] = max(piles[i], piles[i+1]).

The recurrence relation is as follows:

dp[i][j] = max(piles[i] + min(dp[i+2][j], dp[i+1][j-1]), piles[j] + min(dp[i+1][j-1], dp[i][j-2]))

The first option represents the case when Alex takes the ith pile, and the second option represents the case when he takes the jth pile. In both cases, Lee will take the pile that minimizes Alex’s next move, which is either dp[i+1][j-1] or dp[i][j-2].

Finally, we return whether dp[0][n-1] is greater than half the total number of stones. If it is, that means Alex wins as he has more than half the total number of stones.

Here is the Python implementation of the dynamic programming solution:

def stoneGame(piles): n = len(piles) dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = piles[i] for i in range(n-1): dp[i][i+1] = max(piles[i], piles[i+1])

for d in range(2, n):
    for i in range(n-d):
        j = i + d
        dp[i][j] = max(piles[i] + min(dp[i+2][j], dp[i+1][j-1]),
                       piles[j] + min(dp[i+1][j-1], dp[i][j-2]))
return dp[0][n-1] > sum(piles) / 2

The time complexity of this solution is O(n^2), and the space complexity is also O(n^2).

1