🌱 Keegan's Digital Garden

877. Stone Game

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- the number of piles is even
- the total number of stones in all the piles is odd
- since alice can choose first every time, she can choose either the first or last pile
	- this allows her to dictate the subset of piles available to bob in subsequent moves
- because of this, Alice technically will always win, and the solution can just have a return true statement

🤔What Did I Struggle With?

~ probably wouldve struggled with the DP approach, but the loophole in the question meant no issues with submission

💡 Explanation of Solution (Dynamic Programming)

1. define the state
	- let dp[i][j] represent the maximum score difference that the current player can achieve over the opponent, assuming the stones to pick are in the range [i,j]
		- a positive value means the current player is ahead by that much
		- a negative value means the opponent is ahead by that much

2. base case:
	- if i == j (only 1 pile remains), alice can choose that pile
	- dp[i][j] = piles[i]

3. recurrence relation:
	- for each subarray [i,j] the current player can either:
		- take the left pile (piles[i]): the opponent will then play optimally for the new range [i+1][j]
		- take the right pile (piles[j]): the opponent will then play optimally for the new range [i][j-1]
		- therefore:
				dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
			
			- piles[i] - dp[i+1][j]: the player picks piles[i] and subtracts the score difference the opponent can achieve for [i+1][j]
			- piles[j] - dp[i][j-1]: the player piclks piles[j] and subtracts the score difference the opponent can achieve for [i][j-1]

4. final result:
	- the result is stored in dp[0][n-1], where n is the number of piles. If dp[0][n-1] > 0, Alice has a winning strategy

⌛ Complexity Analysis

Time Complexity: O(n^2) as we populate an n*n dp table
Space Complexity: O(n^2) for storing the dp table

💻 Implementation of Solution

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
 
        vector<vector<int>> dp(n,vector<int>(n,0));
 
        // base case: single pile left
        for(int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
 
        // fill the table for all subarray lengths
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1; // end of the current subarray
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }
 
        return dp[0][n-1] > 0;
    }
};

Graph View