Leetcode 877. Stone Game

Problem Explanation

Alex and Lee are playing a game where they take turns to pick a pile of stones from either beginning or end of the row. The total number of stones within the piles is odd, so we will never have a tie. The aim of the game is to have the most stones by the end of the game. We are to figure out if Alex, who starts first, would win assuming both players play optimally.

Now, let us take an example to understand the problem better. Suppose the array of piles is [5,3,4,5]. In the first turn, Alex can choose either from the beginning or end, so he can choose either 5. He chooses the first 5, so the remaining piles are [3,4,5]. Then it's Lee's turn who also can choose from beginning or end, thus he can choose either 3 or 5. No matter what Lee chooses, Alex always has a chance to win by choosing either 5 (if Lee chose 3) or 4 (if Lee chose 5).

Solution Approach

This problem can be solved using dynamic programming. We create a 2D DP array where DP[i][j] represents the maximum stones you can get more than your opponent in piles[i .. j]. 

In the beginning, each player can only select one pile, so DP[i][i] is just the number of stones at that pile. For other cases, the player can choose either from the beginning or end of piles. If the player chooses the beginning, the number of stones they get more than their opponent is piles[i] minus DP[i + 1][j]. If they choose from the end, the number is piles[j] minus DP[i][j - 1].

Since the index i is related to i + 1 and j is related to j - 1, we can fill the DP array from the diagonal (where i == j) up to the top right (where i == 0 and j == n - 1). Finally, if DP[0][n - 1] is positive, it means Alex can get more stones than Lee, so Alex wins.

Python Solution

1
2python
3class Solution:
4    def stoneGame(self, piles: List[int]) -> bool:
5        n = len(piles)
6        dp = [[0] * n for _ in range(n)]
7        for i in range(n): dp[i][i] = piles[i]
8        for d in range(1, n):
9            for i in range(n - d):
10                dp[i][i + d] = max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1])
11        return dp[0][n - 1] > 0

Java Solution

1
2java
3class Solution {
4    public boolean stoneGame(int[] piles) {
5        int n = piles.length;
6        int[][] dp = new int[n][n];
7        for(int i = 0; i < n; i++) dp[i][i] = piles[i];
8        for(int d = 1; d < n; d++)
9            for(int i = 0; i + d < n; i++)
10                dp[i][i + d] = Math.max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1]);
11        return dp[0][n - 1] > 0;
12    }
13}

JavaScript Solution

1
2javascript
3var stoneGame = function(piles) {
4    let n = piles.length;
5    let dp = Array.from({length: n}, () => new Array(n).fill(0));
6    for(let i = 0; i < n; i++) dp[i][i] = piles[i];
7    for(let d = 1; d < n; d++)
8        for(let i = 0; i + d < n; i++)
9            dp[i][i + d] = Math.max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1]);
10    return dp[0][n - 1] > 0;
11};

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool stoneGame(vector<int>& piles) {
6        int n = piles.size();
7        vector<vector<int>> dp(n, vector<int>(n));
8        for(int i = 0; i < n; i++) dp[i][i] = piles[i];
9        for(int d = 1; d < n; d++)
10            for(int i = 0; i + d < n; i++)
11                dp[i][i + d] = max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1]);
12        return dp[0][n - 1] > 0;
13    }
14};

C# Solution

1
2csharp
3public class Solution {
4    public bool StoneGame(int[] piles) {
5        int n = piles.Length;
6        int[,] dp = new int[n, n];
7        for(int i = 0; i < n; i++) dp[i,i] = piles[i];
8        for(int d = 1; d < n; d++)
9            for(int i = 0; i + d < n; i++)
10                dp[i,i + d] = Math.Max(piles[i] - dp[i + 1,i + d], piles[i + d] - dp[i,i + d - 1]);
11        return dp[0, n - 1] > 0;
12    }
13}

All these codes help to solve the problem of stone game by using the same dynamic programming (DP) method discussed above. In each game loop, a player (Alex or Lee) picks a stone (choice at either the beginning or the end) and aims to maximize their individual sum of stones. By looping over all possible choices and utilizing the DP array, these codes help inform whether Alex, the first player, could win the game by obtaining more stones than Lee.

The logic of the solution remains largely similar across different programming languages. Python, Java, JavaScript, C++, and C# variations use an integer data type to store the sum and use arrays to build the DP array for comparison. They all utilize loops and conditionals to iterate over all possibilities to reach a solution. Once the algorithm completes the loop over all possible stone choices, it checks the value of DP[0][n - 1] and determines if it's greater than zero. If it is, the program returns true, indicating that Alex can win the game, otherwise, it returns false.

These codes provide optimal solutions to the problem with clear implementation and good efficiency. The dynamic programming method ensures the minimum time complexity for such kind of problems, making the code efficient for Alex and Lee's stone game scenarios.